Great idea.
Opeth - I guess they fall into progressive death metal. I feel in love with this band after their Morningrise album. opeth.com is their website, I assume you can find some samples of their music there. Their newest album (Ghost Reveries) is very very good. Dont get put off by the fact that they are now on Roadrunner, nothing at all was lost in the movie. Opeth defines what a great progressive metal band should be. Also, their lead singer has the best voice I've ever heard in death metal/progressive metal.
Mr. Bungle - Mike Patton's first band. Downright crazy mix of jazz, metal, circus music, everything and then more. No longer together technically. Visit bunglefever.com, the best place I've found for information about them.
Dark Tranquility - Melodic death metal band. From Sweden (like Opeth), their newest album (Character) is really good, Damage Done before that not so much. But the rest of their albums are really great, Projector and The Gallery being my next.
Bjork - Everyone knows Bjork, if you dont, then look her up, lots of interesting stuff about her. Like her now getting the idea that she wants to sail the world.
Tori Amos -
that's all I have to say.
Isis - A metal band. They create amazing walls of sound, very beautiful and emotional music. Not to much singing, but that's a good thing to me.
Mushroomhead - Ahh, Mushroomhead. Their first three albums are AMAZING. If you like any dub, or enjoy piano mixed with metal, and a whole bunch of weirdness you'll enjoy their first three albums. Truely amazing stuff. Their last album XIII is not my favorite, in fact I though it was very dissapointing and falls very much in line with metal/hard rock. A few interesting songs, but not much. They are suppose to be releasing a new album this winter, I have high hopes.