Depending on how high your bar is set for the word "legal", allofmp3.com fits your requirements. It does have a very nice spyware-free Windows app for searching the catalog and downloading files automatically in the background, but the site itself, including the downloading of files, works fine from Firefox on my Mac. The best part is the files are mp3, encoded how I want them, and DRM-free.

Of course, their site is basically taking advantage of international legal loopholes that make it impossible for the RIAA to go after them, but that's fine by me.