Pandora for iPhone will be a huge hit
news.cnet.com
news.cnet.com
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.
I bought a phone from sprint specifically to listen to Pandora in my car. I can't get it to play a single song stationary in my driveway.
oh well :(