Hrmm, I have always found that last.fm finds better music based on my seeds than pandora does, especially for a discriminating (read:snobby) music junkie such as myself. I remember they had a last.fm app that was usable with jailbroken iphone/touch, that was much better in my opinion.
I have found that to be the case too. This is ironic because (as far as I know) Pandora is powered by data that is manually entered by snobby music junkies employed by the company, while last.fm is powered by data mining.
I've got Pandora on my iPhone, and it's been the most heavily used application installed on it by far. They did a really nice job with the application. It's very intuitive and the sign up process wasn't terrible. Beyond that, it works great over 3G.
It's not so great on EDGE (but fine on WiFi, of course)
It's annoying you can't have it running in the background, but that's Apple's fault.
AOL Radio is nice too.
And check out Shazam. It records a snippet of music from the radio, TV, etc and sends it to their servers for identification (it seems to be very accurate). Midomi is another similar app, but no where near as accurate, from my limited testing.
Had not used Pandora prior to the iPhone application. I'm impressed at how well it picks songs that I like listening to. I'm happy the iPhone application even works over EDGE. Pretty amazing. To have access to the jukebox in the cloud. AOL Radio does not seem to work over EDGE.
Wow why didn't I find out about last.fm before. Friggin awesome service. Have hopelessly been trying to find some good onlineradiostations but having it all in one like this is superb.
Is there any sign of a FineTune iPhone app? I liked their Nintendo Wii interface and I'm disappointed that web on Wii hasn't been as popular as expected