I've been a big proponent of Rhapsody
for a while. It's been two years since I subscribed and not much has changed with the service. It was starting to bother me but then yesterday they released Rhapsody 3.0. It is a huge improvement. In fact the new feature list reads almost like my feature request list, and it was a long list. I actually sent my whole huge list to them a while ago, so it would be pretty cool if I had any role in steering the product, but I probably didn't.
Here's the new stuff I'm excited about, that I asked for and was finally delivered to me. New playlist/library tools. Searching in the list like Winamp j-key. Managing and playing of CDs and MP3s. Lots more columns of info abou track and ability to sort by them. Editing playlists seperate from the now playing list. Rating Songs. Better collaborative filtering and recomendations. The beginning of a community where you can share playlists. Integration of a music store for buying songs. New support for portable devices. A portable device rental service like Napster-to-go. One really cool feature that I suggested but was surprised to see them implement is the ability to take some of your music offline as long as you are still subscribed.
So it you haven't tried it yet, Try Rhapsody