Know what you mean about these pay sites and services you can use for downloading MP3's. Many have DRM which is pretty terrible. For a start, you are often paying near enough the same to download the albums or tracks as you would if you were to go out to the shop and buy a physical copy on CD. So these days, I think DRM is quite pathetic.
I know you can get programs to get around DRM but for the effort, in many cases, it is pointless. Most service such as iTunes and Napster have music downloads up to the quality of 256kbps and I think some very old music you may find on there will be encoded at as low as 128kbps which might well be enough for most people but if you want quality, your better off with the CD and ripping the songs to MP3 format at 320kbps which is what most MP3 players support up to.
In fact, that is what I am doing now with my collection of music. Getting most of it in highest possible quality, though there is a problem, some music I have, I don't have a CD of it so getting it at 320kbps will be a problem.