In addition you may also like to get back the Pandora feature of suggesting similar music to something you already like.

For this you can use Last.fm

http://www.last.fm/

And a great feature of Spotify is that you can add your last.fm account details to it to add it's features into Spotify.

In the end I think the combination of these two sites/applications creates a greater solution than Pandora was. A little sad considering Pandora invented the idea, but as end users the easiest, best designed, and smoothest to use solutions will always win in the end.