Gurren Lagann as others have said.
Cowboy Bebop is beautiful, action-packed, poignant and occasionally quite funny. It also has a very good English dub.
Ghost In The Shell: Standalone Complex is now on its third series. It's stunning to look at, astoundingly well written and has some great metaphysical high-concept plotlines, but you may have difficulty following the ins and outs of the episodes and overarching plots without a flowchart the size of a tablecloth.
Outlaw Star is kind of fun.
Sergeant Frog, original manga and later anime, are both worth a look for a background into Japanese culture from the perspective of an invading platoon of alien cartoon frogs. It's so mad and funny beyond words. The early mangas almost had me in tears, and made for some funny looks from other passengers on the bus.
Somebody further up said 'anything by Studio Ghibli'. They're right. Howl's Moving Castle, Spirited Away and Laputa: Castle in the Sky are my particular favourites. Proper family entertainment, with all the gun-play, evil spirits, giant robots, shape-shifters and armies of steampunk nazis that should entail. Actually, I think that just covers Laputa.
-Nick