Unfortunately, you aren't going to get a lot of good answers -- a majority if not all of those random "MP3 Download" apps are nothing more than fronts for pirated music. There are lots of good, legitimate free / low-cost music sources though. Spotify and Pandora provide free streaming radio on mobile. Rdio, Spotify, and Rhapsody offer reasonably priced subscription services that let you save tracks to your phone to listen to offline.
Hope this helps a little.