Definately watch Berserk… it’s a bit bloody, and there’s a rape scene at the end, it’s still really good. tho, i’ve heard the manga is better (and i believe it) Angel Sanctuary and X are a tad guyxguy-ish (just a tad… not too bad… Angel Sanc is actually really good). Also… never seen this, but… Weiss Kreuz might be good.
… Fshugi Yugi is way too much drama for me… O.O but some people likes it a lot. Trigun is just funny/silly. RahXephon is good… like Evangellion, but without the crappy ending ^^. Witch Hunter Robin seems good, if you’re into darker things (i’m watching that right now…) Cowboy beebop seems nice, even tho i’ve only see the first DVD of it.
If you’re into the fantasy types… definately watch Record of Lodoss War. OVA is MUCH better than the TV series 
Hack Sign…Star Ocean EX
Full Metal Panic is really good…kinda like Gundam Wing with a twist of Comedy.
And who can forget Hellsing?