All I know about the subscription services is that depending on what kind of mp3 player you have, you may or may not have issues with getting your songs to play. As far as legal downloads go, the cheapest place I know of is
http://allofmp3.com/ They're legal, but I'm not sure about legitimate. They operate out of Russia, so have different laws I guess...pretty good prices on music, but I doubt if any of the money makes it back to the artist.