On a friend's recommendation, I signed up for Rhapsody's music service.

I wasn't able to get it working in Linux. The web interface uses flash, but in Windows it requires the installation of some kind of small piece of software, probably to allow playing of whatever audio format (real? windows media?).

I gave up for a week trying to get it to work. Then, it hit me:

1. Every box I've got came with a windows license.
2. rdesktop supports passing sound remotely (-r sound:remote)

This means I can listen to rhapsody on any platform. Using the license on my laptop, I installed Windows XP in a qemu instance on Linux and enabled remote desktop access. Then, simply doing 'rdesktop -r sound:remote' to login to the virtual machine allowed me to play music. Excellent!

Rhapsody's got a good selection and just about everything I've searched for has been available.