Spotify, Rdio and all these other sites need to open up their catalog to local and independent artists. That's one of the reasons iTunes was so popular -- they allowed Youtube singers and other aspiring artists to post their songs and allow people to purchase them. They tapped into this long tail and both Apple and these indie artists made money from it.

These companies can't compete with the big players by offering less. No one cares about the piracy thing, they just want their music, and they want the music they are looking for. 'Social discovery' can be great and all but if I'm looking for a very specific, hard-to-find song, chances are I'm going to find it on Youtube instead and forget about Spotify/Rdio, etc. I think Grooveshark let users upload their own content, but failed in that aspect because their catalog ended up being way too messy.

Difficult problem to solve, wonder who will prevail.

/edit typo