I pay for and use MOG and their recommendations are pretty good. Certainly this could be the case that "everything sucks I am going to execute better than everyone" but it's a sexy problem (not a schlep) and everyone seems to be working on it.

Their recommendations use Echonest, and as far as I know so do Rdio and Spotify. You can access those recommendations via an API for free!

Spotify does not use Echonest for recommendations.

For recommendations, we use our own algorithms. For radio, we use Echonest in some cases, but mostly our own stuff.

There are several sites for music discovery (Boss.dj, Earbits, Beastmode.fm, ex.fm, We Are Hunted to name a few)

Agreed there are a lot of holes in the music discovery experience, I've yet to see a solution that really nails it

Out of curiosity, how do you find out about these sites? Up until now the only one I knew about was Indie-specific (Mixest) and Grooveshark