Can't recommend many of the ones previously mentioned enough (especially the Cowboy Bebop series), though I haven't seen all of them, those that I have (most of those mentioned) are fantastic. Also maybe Metropolis? I still haven't seen that movie yet myself ... maybe by the time it is 100 years old.
Another few greats off of the top of my head that probably fit that most may not have even heard of would be Repo! The Genetic Opera (yes, it is a musical), Dark City, The Thirteenth Floor, 12 Monkeys (which also has a star-studded cast). I know I must be missing some good ones.
Ha, I even forgot about Equilibrium. I had to come back for that one.
If we're getting into anime territory, maybe Gungrave as well? And Space Pirate Captain Harlock, of course.