I'll make a couple recommendations that I don't believe have been mentioned yet. So here are my thoughts, with a little cut and past from Wikipedia mixed in.
Now and Then, Here and There: It follows a young boy named Shuzo "Shu" Matsutani who, in an attempt to save an unknown girl, is transported to another world (heavily implied to be the far future of the Earth, shortly before its destruction). The world is desolate and militarized, and water is a scarce commodity. Now that might sound like a bit of cliche set up but this anime is unusually gritty and the end product is something wholly different than what I've come to expect out of most anime. I will warn you that it is brutal, not so much in what is depicted as what is implied, dealing as it does with child soldiers and the horrors of war. At only 13 episodes it's a good watch without a huge investment of time.
Blood: The Last Vampire: Part horror, part action. It's not terribly deep on plot, but still a good watch. It's a movie so the time investment is small, and it's oh so prettily animated. The story is set in the American Yokota Air Base located in post-WWII Japan, a few months before the beginning of the Vietnam War. Its main protagonist is a girl named Saya, who hunts hematophagous bat-like creatures called chiropterans for a secret organization known as the Red Shield.
Now a few comments on what's already mentioned.
Ninja Scroll: The first anime I ever bought along with Ghost in the Shell (excellent by the way) on the same day. It's a classic and a favorite of mine, but it's not very deep. It's like the Arnold movie of anime, just screaming action from start to finish without much else, but oh what glorious fun action it is. I have to warn though it contains a couple of explicit scenes that some people may not be comfortable with.
Wicked City: It's alright, it's pretty dark and there is some cool actions scene and the like, it's definitely got that old school hardcore action vibe that I associate with 80's anime. But really the only reason I'm mentioning it is because it was recommended and I feel it only fair to warn that it slips into outright pornography at times. This is not a movie I normally recommend especially to people new to anime for fear of it turning them off of it.
Full Metal Alchemist: I love this anime, it slips comfortably back and forth from a lighter humorous side to darker themes. This is one of the very few anime I think is actually stronger than it source material. The manga is good, but the anime just flat out does some things better though they do diverge a fair bit.
One Piece: It starts ok, but I haven't meet anyone that's watched the Nami/Arlong arc and not fallen in love with the show. That is a fair ways in, and its quite a lot of episodes now. A lot of animation is cheap and the filler can be meh. Still I recommend it, it just oozes ridiculous amounts of imagination. However I recommend the manga more, it is oh so good and one of my absolute favorites.
Cowboy Bebop: If you've somehow managed to avoid this one with the amount it has been aired over the last few year, do yourself a favor and watch it.
Witch Hunter Robin: I really like it because of the tone of the show, but I'm not sure I'd recommend it just starting out. The animation quality is at the low end of the spectrum, the pacing can be glacial, and the ending was slightly disappointing. Like I said I like it, but I think I would only recommend it if it suits your particular genre interest.
Samurai Champloo: Slightly ridiculous and totally awesome. Watch it.
FLCL: Fantastically weird and Fantastically animated, and short.
Bleach: There are so many better recommendations here, I wouldn't bother. It's a bog standard, drawn out fighting anime. The genre has stronger offerings IMHO (like YuYu Hakusho).
If you're getting in anime, maybe I could suggest you check out some manga as well. A huge amount of anime started as manga, and most it was better and a lot less time consuming to read than watch.
Some manga recommendations: One Piece, Berserk*, Lone Wolf & Cub*, Full Metal Alchemist, Fairy Tail, Hellsing, and if you like horror anything by Junji Ito*.
*Once again, warning for graphic content.
