SpotOn Radio - Pandora for Spotify Users
Stumbled across this app the other day. It basically delivers the shuffle or genius functionality that most wish Spotify had. It works just like Pandora... pick an artist and it will design a station based on similar artists. You can modify the station with the "thumbs up/thumbs down" voting. The major difference is that you can also export your station to your Spotify account as a playlist. The only downside I've come across so far (albeit a very small one) is that it does not scrobble to last.fm from the app. Obviously, if you export the playlist to Spotify that takes care of that. Also, it does appear to be iOS only at this point.