I've decided to try out both Rhapsody and Zune Pass, each around the same price, each offering a similar service; a music library you can listen to and get an allotment of free downloads per month. I tried Rhapsody first, and quickly realized why I haven't had a Real program on my machine for a long time; they suck. The one really good perk was that I could listen to Electric Six all I wanted. You can never listen to "Gay Bar" enough times. I tried their app on my iPhone, and nothing. I looked on iTunes and quickly saw that almost every review was one star, complaining that the app wouldn't start for them, either. I quickly bagged that piece of shit and tried Zune Pass.
I really like the PC Zune's interface. Much cleaner than Rhapsody or iTunes. But it's a little too abstract, and the simplified iTunes look is still where I'll be downloading and listening to my podcasts from. Also, no Electric Six to stream. But, they do have many other artists to stream, and it's not Real, which is always nice. Plus, if I ever became really crazy, I could buy a really cheap Zune model and constantly switch music in and out of their small flash drive model.
Does anyone know of a better alternative?

Spotify is supposedly the best, but it's not available in the US so I wouldn't know.

For paid subscription services you could try Napster. I tried it, it was alright.

GAH MUSIC SUBSCRIPTIONS
I like the idea but I just don't like being tied to a monthly fee for a ton of music. I'd rather it be like eMusic where you pay a monthly fee to download a set number of MP3s that you own forever.

Since I don't download music on a regular basis, signing up for a subscription service would be a waste of my money. Besides, I want to actually own the music I'm paying for. Instead, I just download a song/album as I go along (earlier this week, I bought my first mp3 on Amazon in about six months). However, I prefer Amazon to iTunes, because Amazon sells DRM-free mp3s.
That being said, if I ever start mass-downloading music, I'll be sure to check out eMusic or Napster. But I already know to stay far away from Rhapsody; I HATED their player when it was on my old laptop, and I can only imagine how bad their subscription service sucks.

Zune Pass is a pretty good hybrid between the "pay anything, keep nothing" services and the a la carte purchase services.
With Zune Pass ($15/month) you get unlimited music plays, and you get to keep 10 songs each month. Basically, you get 10 song credits every month, so you're really paying $10 for 10 songs and $5 for unlimited plays of anything else. If you end your subscription, you get to keep the songs you've selected to keep each month (ex: if you are a member for 6 months, you can still leave the service with the 60 songs you selected to keep).
The Zune Pass is amazing if you have a Zune player. The service integrates well with the Zune device and its wireless capabilities. Napster is less expensive ($7/month, keep 5 songs), but it is now owned by Best Buy. I am not comfortable with any paid service tied to Best Buy, and I am sure that others share that distrust.
For general music purchases, Amazon mp3 is the way to go.
For a subscription service, if you have a Zune, the Zune Pass is awesome. Since you like the Zune software's interface, you should enjoy that choice. If not, you can try Napster (if you're willing to take a risk with Best Buy). eMusic has the worst selection of mainstream artists, so I recommend that people avoid it unless they prefer independent music.
Oh, and if you are considering a Zune, you should look into the Zune HD. Yes, it's more expensive than the older Zunes, but it is an excellent personal media player. It has a fabulous design, extremely responsive touch controls, great playback options, and solid social features. The iPod Touch is the better player if you are looking for a mobile computer, but the Zune HD is a stronger media device.
*DRM notice:
Many stores now sell DRM-free music. All of Amazon's catalog is DRM-free, and most/all(?) of the titles on iTunes are DRM-free. The Zune store is mostly DRM-free (generally, record companies that you can't find on Amazon are avaiable on other serivces, but with DRM), with clear labels for DRM-free tracks (MP3 stamp on every song thumbnail that is DRM-free).

Just remember to download your music, that's all.
I had a crappy period in my life 2 years ago when family crises and illnesses meant my attention was a bit diverted. When I managed to have the time to look at bank statements etc I was reminded I had an eMusic subscription that I hadn't used for 8 months...
Sent them emails and a letter asking them to consider adding unused download entitlements to my subscription, as they could verify on their system that I'd made 0 downloads in 8 months, but they dismissed this.
So yup, I spent £108 on music I didn't download. Totally my fault, but I think it's reasonable to think that no expects to spend that amount of money and not receive anything in return. I would have expected eMusic to understand that and at least offer some gesture to keep me as a paying customer. As a result I've been put off them for life.

eMusic is a good service, it's one of the very few online music services I can use outside North America (I hate you, Amazon/iTunes/Zune). I love discovering new indie bands as well as listening to that one Paul McCartney album OVER AND OVER AND OVER.

Whyyyyyyy

You can download music from Zune's service if a) you put the US as your region in Windows' control panel and b) buy US Microsoft Points. Their music store doesn't seem to do a location check. Haven't tried this for paid music but when they have freebie music I can download it just with my region set to the US.

Really? Wow, I shall try that when I have some points on hand.

Remember they have to be US points, UK or other regions won't work! For me that meant buying them from a reseller to give it a go (I bought a few episodes from Heroes season 2 - boy was that a waste of money).

I use Spotify, paying for Premium.
On a related note, I've got tons of Spotify invites to give away if anyone wants them. Although they are country limited.

Not if you make an account, and then give the account to someone else. :D
Although you'd have to sign in to it every 2 weeks so that spotify sees you're back in an allowed territory.

I personally prefer to buy CD's then rip them with DBPoweramp and listen to them on Creative's Zen X-Fi. It's the best music player on the market, it's just shite at everything else. This Christmas I will be giving myself a Zen X-Fi 2, then those music CD's are being ripped to FLAC and thats the best quality you can have.