I use Spotify as my primary music listening service and their music discovery is terrible. I'll gladly listen to Spotify through Twitter if it means better charts of new music, popular music, etc.
Problem solved!
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.
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.