MOG does what you're looking for rather nicely - just switch on "MOG Radio" and it provides a Pandora-like station with similar artists.

I liked that but have gravitated to Rdio, which doesn't have that option in its mobile app yet - it's much, much faster (at both search and playback) than any of the other services I used. They recently implemented a Genius function in their (excellent) browser client, so I expect it in their apps soon enough...