Higurashi no Naku Koro ni: A very creative and chilling horror story. It's really quite gruesome but not in an "everyone gets slaughtered in huge battles" kind of way. There's a few torture scenes and some murders. It also has a sequel coming out at some point and it just got licensed (which may make subs a bit harder to get) so you'll be able to buy it legally if you want.
Twelve kingdoms: I can't recommend this series highly enough. It's sort of like the Japanese "Chronicles of Narnia" but it is distinctly it's own world. The story takes about 10 episodes to get going (its 45 episodes long) but it really gets going once you pass that point. I suggest that you marathon it (meaning at least 5-6 episodes in one sitting) when you want to watch it.
Haibane Renmei: This series isn't heavily publicized but if you frequent anime forums you'll hear it mentioned quite often when people talk about their favourite series.
Kino no Tabi/Kino's Journey: Another great, semi-underground series. If you like Haibane Renmei then you'll probably like this series. If you don't like Haibane Renmei then you most likely won't want to bother with this. As an interesting note for this series, the action scenes are surprisingly well done. The fights are fast paced and well choreographed.
Akagi:This show is about Mahjong. If you don't know how to play it then you'll either have to learn from a website or read translators notes or this series will seem immensely pointless and confusing. It is kind of obscure and it definitely won't appeal to everyone.
And if you aren't into any of those (they're kind curve balls that won't appeal to a huge group of people but most of the popular ones that I can think of have been suggested) then I also suggest things like: Naruto (Shippuuden just started and is amazing), Bleach, Monster, Suzuka, and RahXephon.