When they were both new, I tried out Rdio and Spotify. Rdio won my subscription hands down and it was long after they'd shut down that I finally bit the bullet and subscribed to Spotify.
Yes, the auto play recommendation algorithm was soooo good.
Queue management, albums as first-class, actually useful social/discovery features—so much good. RIP Rdio.