I love how easy it is to browse for music by record label on rdio. Not something you can do on other platforms and it's a great way to discover new music! It'll be sad to see it go.
For me the killer feature would be a sophisticated implementation of "if you like this song, here are some you may also like". Sophisticated, because the music I like is usually an amalgam of multiple styles, for example jazz-funk-soul. The existing software is way too simplistic right now:
1.it usually classifies music in exclusive styles (soul or jazz, but not both),
2. the recommendations that come up are usually the well known artists, and I am more interested in less known ones (because I am familiar with all the big names already).