Scott,
I'm surprised this post didn't have more replies. The activity in downloading music legally is becoming very competitive... and it's a good news situation getting better all the time. I recently spent a few days downloading music from Napster (napster.com) during a 3 day free premium membership. I was quite impressed, because I got, well, lots of free (and legal) music. BTW, forget what you know about Napster of old, the new is safe, legal, user friendly, and bug free.
Many of the sites provide music in the WMA format, rather than mp3, for whatever reason (microsoft power?), so that's one thing to check out. Depends what you want to do, your player, etc. Here's a site with a recent and very comprehensive review on several sites:
http://bbspot.com/News/2003/12/digital_music_store_reviews_1.html