I imagine the difference is in how you listen to music. Having been a staunch evangelist for Rdio, I've found that the people that really fall in love with it are usually album listeners. If you prefer to listen in more of a radio type setting, Spotify would probably be better due to the improved playlist functionality.

So I guess it comes down to whether you're trying to discover in the sense of finding new artists, or just finding new music to listen to in the moment.