Let's see...I haven't actually watched Cowboy Bebop, but here we go:
I recently finished up watching Baccano! and I thought it was solid. Its biggest flaw is the characters Isaac and Miria - you'll understand about ten seconds after meeting them. They're still a dozen times better than characters of their type, and are usually actually funny, but they're still irritating. I also thought I would have enjoyed it more if it was told in more-or-less chronological order rather than bats*** insane order.
I recommend Durarara!! as well. Yes, it's about a bunch of high schoolers, but it weaves a complicated and quirky story, without as much mangling of the 4th dimension as Baccano.
Fullmetal Alchemist (both versions) is quite good, though what may turn you off is that it does have those "random anime humor" inserts. Despite the slightly inconsistent tone, both of them are very good, although the original FMA has an *ahem* unique ending. FMA: Brotherhood is just plain awesome. What I did was watch Brotherhood first, than go back and watch the original.
Neon Genesis Evangelion is...er...well, it is. It begins as a deconstruction of the mecha genre, but then - via an imperfect storm of budget running out, crazy director, and other stuff - it dips into psychotic psychological analysis. I recommend you find a professional Evangelion coach to guide you through the series. And then I think you watch Rebuild of Evangelion...which I haven't done yet.*
Code Geass is...er...well, it is. It's my all-time favorite anime, but you may find it pretty hit-or-miss. It has an absurdly varying tone, but it makes sense. About half of the anime is about the ACTUAL Japanese Batman acting as leader of a resistance movement. The other, smaller half is about Japanese Bruce Wayne, who, of course, is a high-schooler. Code Geass is basically its own High School Alternate Universe anime. They do do a pretty good job of making the lighter bits give you a stronger insight into the characters.
Basically, the show revolves around three things (in no particular order): 1) exploding mechs: this is Sunrise, what do you expect? 2) LARGE HAM: What would be melodrama in anything else is par for the course in Code Geass. Japanese Batman is a good public speaker. 3) Dramatic irony: the art of creating tension because the audience knows something about a character another character doesn't know.
In a similar vein, Mobile Suit Gundam 00, the only Gundam I've seen.
*I believe the correct way to watch Evangelion is to 1) watch the series, 2) forget episodes 25-26, 3) watch Death/Rebirth, 4) watch End of Evangelion, 5) slash your wrists, 6) drink rat poison, 7) hang yourself, and 8) shoot yourself.