Paprika is one of my favorite movies of all time, let alone one of the best animated films. Satoshi Kon was amazing. His death was a great shock to me.
Carried by the Wind - Tsukikage Ran - sort of like a female Zatoichi.
Paranoia Agent - and everything else by Satoshi Kon.
Read or Die TV - You mentioned Read or Die, but you may not have seen the 26 episode series.
Ghost in the Shell: Stand Alone Complex - Much better than the movie in my opinion.
Rurouni Kenshin - Tsuioku Hen AKA Samurai X: Trust & Betrayal
Kaiba - very strange
Pet peeve here. It’s not Read or Die TV. It’s ROD the TV. Just ROD. As it takes elements from both Read or Die and Read or Dream (which is called that in Japan, as well, not Shin Read or Die as the review on Amazon states), it’s simply ROD, the initials of both of the subseries.
Same here. What a terrible shame.
I deeply enjoyed:
Vision of Escaflowne (Mentioned above)
Last Exile
the original Rurouni Kenshin TV series (up until the end of the Kyoto arc) - though I’m not sure I’d actually recommend this, per se, because there’s a LOT of filler fluff in season 1. x.x You actually only need to watch like…eps 1-12, and then 28-62 or so. Though I guess you could watch 23 and 24 too if you wanted. 
The rest of it is of…variable quality.
I’m not personally sure I’d actually recommend Neon Genesis Evangelion, because while it had some good ideas, I felt its actual implementation was pretty godawful, particularly towards the end of the series. I also found Trigun and Hellsing pretty tiresome.
Reading the manga version of Hellsing, and I like it. The first time I’ve seen fanatical Anglicans in a modern setting. 
For dark and quirky:
Shinreigari: Ghost Hound – Uh, I’m not even sure how to explain this one. Astral bodies, weird science, therapy and nightmares. It’s quite slow paced and an acquired taste, somewhat similar to Lain with its atmosphere.
Haibane Renmei – Dead souls idle in some sort of purgatory, waiting for something to happen. It’s been a long time since I saw it so I don’t really remember exactly what happens, but I remember that I loved it and that it was certainly odd.
Ergo Proxy – A few remaining mega-cities dot the surface of post-apocalyptic Earth. Then the status quo is shattered. This had a few filler episodes, but some parts of it were strong enough to compensate for that. A bit confusing ending but that’s more a rule than an exception with anime.
There’s indeed tons of this stuff, all sorts - sci-fi, fantasy, horror etc. And I’ve seen at least one episode of most anime aired in the last 10 years or so. I like to check stuff out even if I know I’ll hate it, just to see what completely insane stuff they’ve gone with this time. Anime Database is a pretty good place to go search for things you might want to watch. This is my favourite anime blog and it has a huge amount of reviews archived. If you want to know something specific feel free to PM me, too. Whatever you choose to watch next, enjoy! 
Really, first pick a genre. Do you want science fiction or fantasy? Then most of what has been listed above is definitely worth watching. I don’t watch much anymore; don’t have the disposable income to want to buy, refuse to watch a dub (so that takes out Netflix Instant), and forget to put it in the queue. I should, but anyway.
Anyway, as I said, pick a genre. If you’re interested in science fiction or fantasy, other shows worth watching that haven’t been listed include Gunbuster, Serial Experiments Lain, maybe something like Martian Successor Nadesico if you want more of a comedy. I like Sorcerous Stabber Orphen and the Slayers series are pretty much classics in the comedy fantasy area.
Slice-of-life shows include things like Niea Under 7, His and Her Circumstances, and I’m sure a whole slew of others.
There’s the whole magical girl genre; I think most would agree that Cardcaptor Sakura is worth watching.
For pure weirdness, there’s always Excel Saga. Either know an awful lot of anime or watch it with the pop-up notes on to explain the references.
Lupin III is fairly popular as well.
Just a few off the top of my head.
I cannot recommend Steins;Gate strongly enough.
Steins;Gate
Steins;Gate
Steins;Gate
There!
I also recently loved Usagi Drop about a 30-something single man who adopts the illegitimate daughter of his recently deceased grandfather. Only 11 episodes, but if heartwarming is what you seek, here you’ll find it.
Speaking of heartwarming, I also loved Hanasku Iroha, about a young city girl who goes to live (and work, she finds out) at a country inn run by her grandmother.
So as you can see, lately I’m loving slice-of-life stuff, but if you like a little fantasy with yours,** Air**, Kannon and Clannad are hard to beat.
And for sheer beauty all the way around, see both seasons of Aria, about young girls training to be gondoliers in a replica of the city of Venice on a terraformed Mars of the future.
I think the best shows of last year were; ** Steins;Gate** (time travel), Ano Hana (fantasy) and Puella Magi Madoka Magica (magical girl). All fantastic!
Card Captor Sakura is unbelievably watchable, even for people who don’t have an interest in the genre. It’s kinda bizarre.
I only really liked Castle of Cagliostro; The rest of Lupin always seems better at one remove.
I forgot to mention Mushi Shi and Baccano! in my previous post though.
I forgot about this one. I bought it solely because of the cover art and I loved it. Not much action but very interesting. The purgatory is a city with some open land around it and then a wall completelybuilt around that. The souls are not allowed to go outside the wall. The souls have bodies and live off in the countryside part of the town. The souls are not allowed to earn money so they do chores and good deeds around town for credit and then use the credit to buy clothes and food. Eventually “something” happens and a soul is released. Like I said not a lot of action but a good thinker.
Don’t forget Case Closed: Detective Conan if you like Agatha Christie or Sherlock Holmes.
A second vote for Last exile. The world was strange and trippy.
Ranma 1/2, My favorite anyway.
Not sure how to categorize best as anime is a pretty diverse category.
My faves list of series…
Melancholy of Haruhi Suzumiya: Wonderful characters, great humor, and an interesting story arc. The second series and movie aren’t as fresh and enjoyable, but the first series is amazing.
Inuyasha: Great fantasy and creative action. Gets somewhat repetitive after a while but holds up well for far longer than expected.
Haibene Renmei: Mentioned in thread already, great thoughtful series.
Samurai Seven: A retelling of the 7 Samurai in a post-apocalypse giant mech world.
Full Metal Alchemist: Dramatic tension and action at its finest. Note, I haven’t seen Brotherhood yet, so I can’t compare the differences.
I thought the Haruhi movie, “The Disappearance of Haruhi Suzumiya” was one of the best anime movies ever made. It’s one of my favorite movies of all time.
Another vote for Puella Magi Madoka Magica and Steins;Gate.
I’d also recommend:
Angel Beats, if you love a mixture dark, quirky, and a bit of humor, than this series is for you
Baka to Test, one of the funniest anime I’ve seen
Kore Wa Zombie, mix of humor and light ecchi, though it does have some dark bits (the main character is a zombie after all)
Sankarea, romantic comedy starring a zombie girl. Like Kore Wa Zombie, except a bit more dark and fanservice-y
Ore no Imouto, comedy
Haiyore! Nyaruko-san, comedy with Lovecraftian elements
Boku wa Tomodachi, humor and some fanservice
A Certain Magical Index, mix of comedy, sci fi, and drama. Something for everyone.
A Certain Scientific Railgun, spinoff of Index.
Daughters of Mnemosyne, drama about an immortal woman who works as a PI. Lots of action.
I only mention it because you said you like dark, but watch School Days to see a harem anime with the bleakest ending ever (or best, depending how much you despise the main male character at the end).
The Haruhi series is also pretty good, except for the whole “Endless Eight” arc. I get they were trying to show what it was like to be in a Groundhog Day like time loop, but did they really need to tell the same story, over and over again, over eight episodes? If you’re watching the second series just watch the first and last episode–trust me, you’ll save yourself a lot of tedium and annoyance and you won’t be missing anything.
I still DVR Inuyasha when it comes on early Sunday mornings.
Among websites that review anime, my favorite is Them.
Recommended Movie:
The Girl Who Leapt Through Time
Recommended Series:
Corpse Princess (Shikabane Hime) - Starts out as monster of the week but gets better.
Series 1 of The Melancholy of Haruhi Suzumiya
The movie is also good. Only utter freaks like myself enjoyed Season 2. Seriously. Season 2 was universally panned.
Eden of the East
Mushishi - reflects some of the best aspects of manga/anime, the ability to create an immersive world. Solid dub.
Evangelion - the TV series
Controversial, but nonetheless a classic. Highly influential. Bigger than Star Wars in Japan. Grossed something like a billion dollars, including merchandise of all kinds. I would argue that it represents the 2nd greatest combination of artistic and commercial success of the 20th century, the first being Lord of the Rings by a wide margin. There are bigger hits and better works (oh yes, there are). But few that are both at the same time.
Gurran Laggen - Epic. A more optimistic take on some of the Evangelion themes. Gainax meets Looney Toons.
Cowboy Bebop
Haibane Renmei
Spice and Wolf Season - medieval economics
Elfen Lied - Gory horror flick, moving in an odd way.
His and Her Circumstances
Shonen:
Naruto - Series 1, at least the parts that are not filler. The filler (i.e. the parts that weren’t originally in the manga) was awful. Be sure to skip the dub: subtitles only.
Hunter X Hunter
I also liked No Need for Tenchi: sue me. I thought the whole summed up to more than the sum of the parts. The parts summed up to… well not very much.
One aspect of taste is what you don’t like. I couldn’t finish these series:
I wasn’t too keen on Zegapain: I spotted plot developments a mile away.
I couldn’t get through Paranoia Agent either. Odd: I usually like sardonic works.