Last time I checked, Pandora's catalog was far too limited to be valuable to me for discovery. It was easy to come up with a half a dozen artists I like that Pandora had no clue about.

To me the word "discovery" means finding unknown works, not simply another way to listen to an artist who is already well established.

Pandora for discovery is a nonstarter, at least for me.

My dream wish is if someone could make a Pandora-like app ( both of in terms of functionality and quality) built on top of Spotify. I know spotify offers some API but don't know if this would be possible.

IIRC Pandora has a catalog size of about 1 million vs ~20 million for Spotify and yet they have been able to do a superb job in song recommendations. I find Spotify radio to be pretty terrible at this.

+1 for pandora. +2 for waffles.fm and what.cd ;)