AlbertCole: ... and my mind is blown. Especially "The Second Renaissance" flashed me hard. I wouldn't have thought that it would be so intense. After I had seen "Final Flight of the Osiris", I thought that these short films surely are overvalued. But then... POW! I sat in front of my TV, blown away, speechless. The Sequels could have been so much better. So much potential given away.
In retrospect, I think the Animatrix was a tad overhyped. I too loved The Second Renaissance (and Matriculated comes to mind as well, for it's Aeon Flux-esque visuals) but even at the time it came out it looked to me like it was a cynical marketing ploy to keep up interest in the Matrix, series with all of the buzz surrounding Reloaded and Revolutions. I personally think that they should have had more stories, or made them longer, to make the entire collection feature-length (I think it was 30-45 mins., IIRC).
Fenixp and
amok pretty much share my taste in anime from what they recommend, so I totally second their recommendations. I would add though Ghost In The Shell 2: Innocence, in addition to the original Ghost In The Shell. If you want more dystopian cyberpunk-ish anime, Akira is also worth a watch.
I have a special place in my heart for Wings of Honneamise. It's one of the finest anime films ever made, IMHO. It's best viewed in a pensive mood though, because while there are some good action sequences it's not an action movie by any stretch. Same with Jin Roh, which can get pretty depressing near the end.
If you're going to watch Neon Genesis Evangelion (and you have been warned; it's a very demanding anime to watch because you'll be driven into fits of frustration and WTF moments), I'd actually recommend watching the Rebuild of Evangelion series instead of the original. The plot in Rebuild is a little more coherent...
Death Note was a fantastic show, but you do have to make allowances in your mind for fanservice moments and the appearances of some stereotypical anime tropes. *cough*
Misa*cough*.