Rdio, like
Grooveshark and
Spotify, lets you listen to millions of songs, ad-free.
Their new desktop client looks at home on elementary OS. You can browse through "New Releases" and "Top Charts" for new artists you may enjoy. Or you can search for oldies that you love.
You may encounter some difficulties closing the app. Each time I tried, I got a prompt to force quit the application. After awhile, however, Rdio does close on its own.
If you want it:
sudo add-apt-repository ppa:sgringwe/rdio
sudo apt-get update
sudo apt-get install rdio