For the record, here are my must-sees:
Azumanga Daiyoh (offbeat high school comedy, minus the boys)
Fruits Basket (modern day girly drama/comedy)
Trigun (sci-fi western)
Slayers (medieval fantasy parody)
Cardcaptor Sakura (classic magical girl - but only watch the subtitled, DVD version)
The Melancholy of Haruhi Suzumiya (modern-day sci-fi parody - better if you see a variety of other anime first)
Genshiken (realistic comedy about otaku college life, also funnier if you see other anime first)
Detailed genre descriptions after each title. Basically, if you like that genre (or something similar to that genre), I'm pretty darn sure you'll like the series I listed.
I made sure not to include anything without widespread appeal.