I've used Pandora for about a year now and I find it the absolute best of all the apps/sites that create custom music channels for you. Pandora doesn't just settle for "artist a is similar to artist b" in populating its channels, they've actually gone to the trouble of rating individual songs by a series of descriptive categories and then they use these song characteristics to figure out what you like or don't like. In my experience there channels 'learn' your tastes much faster and more accurately than similar services.
I was very, very happy to see they have an app out for the iPhone!
🙂