About Pandora (Download Link)
Pandora is a part of the Music Genome Project and allows you to create "stations" of your favorite artists. Pandora then pairs those artists to others you might like and plays an unlimited playlist based on your favorite artists. Pandora tracks your likes and dislikes and will play songs based on those results. Pandora lets you find new music for free, and who can argue with that?
About AOL Radio (Download Link)
AOL Radio is a CBS Radio partner that provides online streaming radio stations. Unlike Pandora, AOL Radio is a true streaming radio station in the sense that you can play local stations which support in-audio advertising. AOL Radio can use the location feature in order to find CBS affiliate stations that bitcast near you.
Both Pandora and AOL Radio follow a similar user interface design: they both look like the iPod feature on iPhone/iPod touch. Both of the interfaces are nice, however, I have the same gripes for both. The volume controllers in both seem to be independent of the iPhone's volume controller. This can cause the audio to be distorted if you turn it up too much in the applications themselves since you can use the volume buttons on the side to control the audio volume as well.
Secondly, I would love to be able to quit the application and have the audio keep playing (I know, this is an Apple/SDK restriction, but it would still be nice). You can, however, lock the phone and keep the audio playing (which is a nice feature).
Both applications allow you to purchase the currently playing song from the iTunes WiFi Music store. AOL Radio also provides a link to find out more about the currently playing song on AOL Radio's site.
WiFi (or 3G) vs. EDGE Use
When you are playing the music over WiFi (or the 3G cell network), you get awesome audio quality. Both applications seem to provide audio quality that matches that of purchased iTunes songs. On EDGE, however, AOL Radio falls short by providing very low quality audio (I would guess 56k audio). However, Pandora on EDGE seems to maintain good audio quality when you have a signal that is greater than 2/5 bars.
So, who wins?
Since both of these applications are absolutely free and have equal pros and cons, I would recommend downloading both to see which one fits you the best. If you are on a 3G iPhone, both will work well no matter where you are (assuming you're within 3G coverage). However, if you have a 2G iPhone, you might prefer Pandora because it provides better audio quality over EDGE. You can download both applications by clicking the download links above.
Disclaimer: The Unofficial Apple Weblog and AOL Radio are both owned by AOL.