I third(fifth, whatever) Cowboy Bebop. The movie Knocking on Heaven's door is sometimes even better.
Same goes for Last Exile. The visuals are amazing and the idea behind the world quite ingenious. Well worth watching.
I also recommend Witch Hunter Robin. It's a sort of a detective series, but with the "detectives" being withces hired to hunt their own kind. The main character is fairly angsty for being a girl who can materialize flames with a nod, but otherwise the story rules. Can be a bit twisty sometimes.
Then there's Ghost in the Shell sequel, Innocense. Quite grabbing and feels even more Asimovian then it's predecessor. The visuals are of course, grand. And so is the soundtrack.
Samurai Champloo has to be one of my favorites ever. Fun as heck with great action artistic direction. I love the mix of thematic elements(daimo/hip hop) they used. Featuring probably the most original cast of characters ever. Except Jin.