If you happen to have a symbian phone, there is a music leeching application that seems to me remarkable, and I'd love to see it cloned on the NITs.
The app is Audials Mobile, from http://www.audials.com and it is possible to download a demo version which allows to download for free 2 tunes per day (while the registered version has no limits).
Basically, this app is a specialized search engine for online social radios, which allows both searching for Author name and browsing for music genre. You get then a list of titles and you can download songs on your phone; downloading speed is enough and the majority of tunes are mp3 encoded at 128kb.
The software house says that downloading from these sites is legal - I am not completely sure, but if there is some guilt, I don't think it's in the end user who sees a link and clicks it.
There are several sites you can download from; I installed the last plugins collection and it looks for music in the following sites: Esnips, GarageBand, ProjectPlaylist, Tagoo, TuneFinder, Wrzuta, Kohit. If you have installed the program on your s60 phone, get the plugin at http://bit.ly/mDZTW then copy it somewhere on your phone's filesystem and load it from the program's interface.

As I told before, I'd love having something similar on my tablet. So, if a developer is sitting without finding whatever the next killer app he is going to code, well that's a suggestion

As a disclaimer, I have no connection with that site, I only liked the program to the point I registered it.

Just curious: how does this app compares to http://getsongbird.com/

You might want to check out sites like Hype Machine, which aggregate mp3s posted to music blogs around the web which you can download.

You don't even need any software to download mp3s as they have an RSS feed of all the latest posts. Just follow the link through to the post and there's your mp3.

Not quite the same thing, but just an idea.

@qgil: I installed a songbird package for ubuntu and briefly tested the app. It's not comparable to audials mobile - as far as I could understand, songbird is a musically-oriented browser with plugins, and a media manager and player.

Also, @zerojay, I knew the Hype Machine but it's just one of several sies that could be searched.

For portable devices, and for a simple task like searching music, bloat isn't good. One simple app like the one I reported might be quicker to fire when you want to get a tune. It makes me remind Napster even if it's not as comprehensive - but I find say 75% of what I like.