My own recommendations, with an attempt to explain why I liked them.
Vision of Escaflowne: Fantasy, with mecha. A young girl from modern Japan is transported to a fantasy world, with magic, beastmen, superscience and giant robots powered by the hearts of dragons. She gets caught up in a war between nations and in romantic intrigue, as her own precognitive powers prove the key to what's happening.
Not the most original premise in the world, but the plot is handled exceptionally well. It avoids the cliches, and has some really surprising plot twists that make perfect sense. A word of warning, though--the English dub is awful, the original voices with subtitles is much better.
Noir: Contemporary, crime, conspiracy. Two female assassins (one a professional killer, the other an amnesiac girl who knows how to deal death, but not where the knowledge comes from) make an uneasy alliance to try and unravel the secrets in both their pasts. However, this search leads them into a murky conspiracy, where it turns out that their histories and meeting may not be as chance as they seemed.
Very good, atmospheric, and refreshingly understated, with the action largely staying in the realms of the plausible and crumbs being dropped at the right pace to retain interest in the big plot.
Excel Saga: You really need to have seen some other anime shows to get the most out of this, as it takes the form of a satire of the cliches of other anime genres. The plot concerns ACROSS, a secret society that wants to take over the world for nebulous reasons, and the titular Excel, it's incompetent operative. That's really just a framing device for bizarre paraodies of everything from war dramas to mecha to martial arts to sports to the Power Rangers. The first episode isn't very good, but after that it's almost solid gold.
On the others, both Hellsing and Berserk were adapted from long-running manga series, and have different endings. Hellsing's ending wasn't very satisfactory for me, but there's a newer series in the pipeline that's more faithful to the manga (with the Nazi vampires and katana-wielding warrior nuns). Berserk the anime has an almost completely different focus to the manga, so the ending comes out of left field for a lot of people, from what I've seen.
(edit--remembered one)
Azumanga Daioh is a new favourite. It follows a motley group of friends (and their teachers) through high school. It's kind of hard to sum up why it's so good in a summary, but it is a great mixture of funny and poignant, with great characterisation and some moments of brilliant, surreal comedy. As an aside, I've often heard the character of Osaka cited as an example of someone with AS, and I can see some traits in common there.