I’m a fan of Google Play Music. The radio does a better job of finding relevant music than Spotify and the Android app feels much more responsive. It also handles network connection issues much more gracefully (important as my commute to/from work goes through a few dead spots).
However, there’s one major part of the UX that bugs me – the albums and playlists displays can’t cope with long titles. In fact they can barely cope with short ones.