Off the top of my head (and a lot of these are dupes of other people's picks - y'all got good taste, folks!)
Samurai Champloo
Cowboy Bebop
Flag
Evangelion (though I have a problem with the very end, which I did not find "deep" and gave me a severe case of WTF)
FLCL (my anti-drug, since you don't need drugs if Gainax is going to perform weird trips for you)
Gankutsuou (jaw-dropping, eye-popping, superflat style animation)
Peacemaker Kurogane
Wolf's Rain (if you have someone who thinks anime is all mecha and and big-eyed girls in maid outfits, this is a good anime for grown-ups to show them. Same with Flag.)
Paranoia Agent (another trippy-ass anime, and also definitely not for kids)
Eureka 7
Naruto up through, what, episode 85? And then it is nothing but filler of the most soul-withering sort through the end of the series. Naruto Shippuuden, the restarted series, is better than the filler, but then a Windows 95 screensaver is better entertainment than Naruto filler. I watched a large portion of the filler out of morbid fascination with just how bad it could get. Hours of my life heedlessly squandered.
Samurai 7
Bleach up through episode 65 or so, and then it pulls a Naruto, though not as bad as Naruto
Ouran High School Host Club - I less-than-three this show so much, but if shonen-ai makes you uncomfortable, a lot of the jokes in this show may make you squirm.
Gantz is pretty good, but pretty violent, and kind of mean-spirited.
Chevalier D'Eon - The people have regular-sized eyes! and also plot, dialogue, and pretty good animation!
Basilisk - this is the real ninja show. This show kicks Naruto's ass, takes his lunch money, then duct-tapes him to the flagpole in front of the junior high school, and posts video of the whole thing to YouTube.
Deathnote - the anime is good, the manga is better.
Fullmetal Alchemist
Full Metal Panic (not to be confuses with Alchemist - totally unrelated)
Ninja Scrolls is an anime classic, which I recommend more on reputation than personal enjoyment. I have a personal history with Ninja Scrolls, which I watched after unwittingly eating something that had been dosed rather heavily with something else, resulting in a very unpleasant 36 hours for me. Now I just can't watch it.
My-HiME
Welcome to the N.H.K.
Afro Samurai