I like WunderRadio. Having local weather and traffic reports immediately available is a boon. There is nothing in the Canadian App Store called 'Pandora.'
Fstream Fstream is great! You can add almost every streaming station, no list or so! Only that it's French and they don't translate the updates always, but the program itself is English!
Besides Pandora, I personally like Radio Box. There are a ton of stations and you can shake it to randomly choose one for you. I believe its a paid app though.
Ok, for anybody outside of the US, Pandora is not available. The Music Genome Project obviously couldn't get licenses for every country. Try Last.fm, which is ok, and is fairly similar in picking songs. The Music Genome Project is the database that runs Pandora, FYI. Just in case you didn't know..
I was using Pandora way before the app came on my computer, and when it came out it became easily the best radio app available.
