MrPatience said:
I can't beleive that no one has suggested 'Excel Saga' yet.
Fits the bill perfectly. For anyone who hasn't seen it, it will blow minds.
This I wouldn't recommend unless you're familiar with anime already.
If you're looking for comedy, Excel Saga is all you need. But it gets about 10 times better when you've actually seen a bunch of famous anime and understand most of the jokes and parodies.
Other than that, I'd recommend;
Hajime no Ippo (boxing, but not the way you'd expect it)
Last Exile (has a high rpg-esque feel to it)
Great Teacher Onizuka (mostly comedy, old, but real good)
Any Gundam series, The 08th MS team is a nice starter (mecha, war, mostly good writing too)
Full Metal Panic (mecha, drama, comedy, it pretty much has everything. Don't confuse it with Fullmetal alchemist, FMP is way better)
Also, just watch the movies Akira, Ghost in the Shell 1 + 2, Ninja Scroll, Patlabor II, Perfect Blue and Spirited Away. They'll give you a fairly varied peek into the vast world of anime.
Perfect Blue should be on your list either way, it'll change the way you look at animated film.