While I agree that 128Kbps MP3s are not really up to scratch, it's worth noting that at least one online music vendor, Magnatune, lets you download your music in a number of different formats, including two lossless formats, and a couple of higher-than-usual-quality lossy formats. More should follow their lead, as I've not been happy with the quality of files from another online music vendor.
I first became aware of Magnatune from an article in Linux Journal, by Magnatune's John Buckman, describing their infrastructure and philosophy. The article is now available from the Linux Journal site. Well worth a read if you're the music-buying geek kind.