I've been looking for a long time to find a replacement to the evil iTunes. And thanks to Jeremy Z's question, and a nice commenter I've found it!

It's a Russian company selling music for $0.01 USD per meg of music. They let you dynamically compress the songs into any format that you want (MP3, OGG Vorbis, MPEG4, even FLAC, and raw CD-DA!!!) so you can pretty much control the price.

It requires no special software, works in a browser, is fully cross-platform, and has a decent selection. This thing is the way music was always meant to be had, but never was. I'm sold.