I tried the Amazon MP3 beta store two night ago and came away pretty impressed. While the UI is not as slick as the dedicated iTunes application, searching, purchasing, and downloading music was very easy. I bought a few Amy Winehouse tracks, and the music was 89¢ or 99¢ a track, ripped at 256 VBR MP3 (LAME-encoded), came with album art, and no DRM. You have to download an app to buy full albums on Windows or Mac OS, but other than that, pretty good experience.
Also try http://www.bleep.com if you’re looking for hard-to-find electronic/techno music. Cheap and no DRM. Most are 320Kbps mp3s or Flac files.