What are the great iPhone apps to discover new music? Back in the days I used Last.fm suggestions  but they are way too generic and aren't useful to me anymore.  I switched to RYM and its recommendation engine is much nicer, however I'm also looking for some iPhone apps that would allow me to discover awesome new music on the go.

I'm looking for these features:


an easy way to browse through artists and albums;
a wide range of non-mainstream artists;
a recommendation engine and/or a smart “similar artists” engine;
track previews (at least 30 sec.);
no limitations on total preview play count;
no need to subscribe to any paid service;
ideally, reviews for selected albums;
some kind of bookmarking to store my findings.


I don't care for the price if the app meets my needs.
What does AppStore have to offer?

Please, post one app per answer.
Discovr is a great app for this. You just enter the name of an artist, and then a list of related artists appear. A network graph appears with all of the artists. You can play previews, and watch videos. Pretty decent app.