eMusic constantly has promotions where they give away songs for free-- any song you choose. The constant promo is 50 free mp3s, but there are also 100 or 125 song giveaways just for giving it a try (does require a CC at sign up, however). The music they carry is a bit less mainstream but if you know what you like you can find it or more artists like it. Some bigger names that they have right now-- Spoon, Modest Mouse, Interpol, My Chemical Romance, Badly Drawn Boy.. and of course, lotsa artists that most people don't know. But don't discount them!
eMusic also has a subscription based service so that you can listen to tons of songs... but I personally don't like that kind of service. I prefer to purchase the 'right' to own a copy of the song (like iTMS).
A thread discussing other iTunes
alternatives can be found
here.