http://www.lala.com
Their streaming business model sucks, but they have some unbelievably cheap MP3's. 79 cents a piece, 7 dollar albums.
Once you buy a song from them at their reasonable prices (just got a 20 song album from 7.50 that was 10 bucks at Amazon), you get unlimited streaming of that song, so you don't need to bring your music with you. Nice touch.