For one thing: user interface. The one of Rdio is pretty confusing, whereas the one of Spotify is, for me at least, the best UI of a music player ever. That's the great thing about Spotify (and I think it's often overlooked): it's not only that their idea is great, but also that the execution of that idea is stellar (for the same reason I prefer Spotify over Grooveshark).