I'll only recommend things I've seen, so this list may get a bit skewed toward the end.
Good, mainstream, "safe bets":
Eden of the East - most recent thing by the director of GITS:SAC, set in the very-near future (it's the series I was talking about when I said that cranky client had been watching too much anime, because the single new technology that's important to the plot is an image recognition/search engine that works)
Dennou Coil - has been described as "if miyazaki did ghost in the shell". Features cutesy kids; setting is a similar-to-real world but with a pervasive cyberspace overlaid on the real world, AR style, and quite magical in tone/feel (but with a dark side). Very good mystery build up, but then a terrible ending that doesn't resolve anything.
R.O.D - Read or Die - short (3-episode) OVA. Sillier in tone, featuring the antics of the british library secret service as they try to prevent a cloned Beethoven from killing the world with music. Almost James Bond in feel, awesome theme music.
Weirder stuff:
Kaiba - series about a world where memories can be switched between bodies, similar to the works of Richard Morgan. Retro blobby animation style to fit with the amorphous feel; weird but cool memory-alteration storyline
Ghostory/Bakemonogatari - in some sense more fantasy/horror/supernatural than science fiction, but it has a sci-fi-like feel, or perhaps more X files. The story mostly just provides a framework for shaft, the studio, to show off their extremely stylized animation; this show is the single greatest argument that animation as an artform is still revelant in this age of CGI, because everything it does would be impossible in any other medium.
Paprika - uses some stylistic weirdness and very good music to tell a story of reality and dreams blending together.
Personal favourites:
The Melancholy of Haruhi Suzumiya - my favourite series, bar none. Is the ultimate expression of the "one assumption" method for writing science fiction (i.e. you make one single unrealistic assumption about the world and then fully follow through on its consequences), though at times it can be more philosophy than direct sci-fi. While I love this series it's probably worth leaving it until you've seen a few other anime, since it's very medium-aware; also make sure to watch it in the original broadcast order, which is not the same as the DVD order or the chronological order (and only bother with the second series if you're particularly struck).
Royal Space Force: The Wings of Honneamise
Getting old now (this is the first production Gainax ever made), this tells the story of the first man into space in a world that's almost, but not quite, our own. It manages to be a reflection on the nature of heroism and how reality is rarely as neat as fiction, and yet at the same time tells a truly heartwarming story of human achievement.

Things I feel obliged to mention (but would personally suggest avoiding for now):
Cowboy Bebop, space opera with a jazz theme. Similar feeling to firefly in some ways (the protagonists are somewhat grey morally, and always short of money). Lots of people love it, but I personally could never get on with it, and still haven't seen the whole series.
Neon Genesis Evangelion: Rightly considered a classic, but it's ageing now (unless you wait for the new 4-movie version to finish coming out); combines your standard "giant robots piloted by schoolkids" premise with a lot of Christian imagery, and then gets gradually more psychological as it goes on, cumulating in the most twisted ending ever.
Ergo Proxy - I think this is the most perfect visualization of the Phillip K. Dick aesthetic I've ever seen - a future dystopia gradually decaying, with people either insulated in the totalitarian domed cities or barely surviving on the surface. It's wonderful to look at, and has a certain elegance to the story, but the show does drag towards the end.
Crest of the Stars - people will tell you this is a classic of science fiction and you should watch it. These people are wrong.

Moving out of the science fiction genre proper:
Gankutsuou (Space opera, kinda) - a retelling of The Count of Monte Cristo, set in the future, and with a unique visual style (the characters move but the patterns of their clothes stay stationary). Probably getting a bit dated now.
Starship Operators (Space opera) - this is pretty much your standard "group of people in a spaceship fighting" premise, but done very well. Has a clever conceit (the crew have to fund their fight by selling the reality TV rights) and remains remarkably scientificly accurate; I love the story.
Code Geass (uh, action, I guess) - famed for its ridiculous plot twists, tells the story of one man's attempt to liberate Japan from the evil Brittanian empire. Very much a battle-of-wits series, similar in many ways to Death Note (which you mentioned). Some robots but they don't become huge until the second series.
Tengen Toppa Gurren Lagaan (Giant robots) - ridiculously over the top approach to giant robots, made by the same studio as Evangelion in a pretty much direct refutation of its angst-filled, emotional approach. TTGL is all about becoming stronger and stronger by sheer force of will, and never takes itself too seriously.
Kino's Travels (fantasy?) - a girl and her talking motorcycle journey through countries with various strange customs, never spending more than three days in each. Has a sort of star trek feel to it, and uses its conceit to get a bit philosophical at times.
Secret of Cerulean Sand/Patapata Hikousen no Bouken (victoriana) - lighthearted, almost childish tale of a girl's quest to discover what became of her brother. Has a bit of a flight aspect to it, and reminded me of Around the World in 80 Days in feel, but also does have a technological theme; I'd almost compare it to Sky Captain and the World of Tomorrow.
Mai-Otome - the internet disagrees with me on this one, but I think it's a really good series. Sharing the same characters as My-HiME (which you should possibly watch first, though that's even more explicitly a magical girl show), this tells the story of a half-futuristic, half-fantasy world, where an elite have the effectively magical power of nanomachines. I love the very realised world with its own politics. The show can be a little heavy on the fanservice at times, so avoid if you're offended by that.

Moving even further away from science fiction:
When They Cry/Higurashi no Naku Koro Ni (horror) - incredibly atmospheric series. Half of it is very sweet, innocent schoolkid antics, which makes the impact of the other half, some very violent horror, even more intense. Also has the most consistently high quality openings and endings of any series I've seen.
Spice and Wolf (fantasy) - half character interactions, half medieval economics. (Yes, really - it's surprisingly good).
Allison and Lillia (I would say dieselpunk, but it's far too optimistic to be any kind of "punk" - so fantasy) - a fairytale played beautifully straight, and largely about the joy of flying, in a sort of WWI-era-equivalent fantasy world. Not science fiction in any sense, but I enjoyed the very different world it portrays.
Aria (healing) - a series about the daily lives of gondoliers on mars. Virtually zero conflict, very relaxing.
Ga-Rei: Zero (urban fantasy) - demonhunting series, though focusses quite a lot on the relationships between the characters.
Absolutely Lovely Children (magical girl, maybe?) - tells the story of Japan's top three psychics, who happen to be ten year old schoolgirls. Surprisingly intelligent, and always funny.
Gundam Seed (robots) - this probably isn't actually much good, but I have a soft spot for it as my first anime. Almost a high school drama in many places, but has good characters and a sufficiently interesting storyline.

Feel free to ask for clarification about anything in particular. If you start moving beyond science fiction I can recommend good anime in other genres (Honey and Clover springs immediately to mind), and if you go further into science fiction I can mention the quite good series that didn't make this list (Macross Frontier, Eureka Seven and indeed Macross Plus), and the terrible series you should avoid (Divergence Eve). You can find my anidb page at http://anidb.net/perl-bin/animedb.pl?show=userpage&uid=205381; for any series which I've watched in the last year or so I will have written a review on that site.