Yeah, I love Grooveshark but their recommendations are bad. I'd love to try Pandora. Not having much choice I'm happy with iTunes on desktop, Double Twist and Grooveshark for mobile. I've dipped my toe in Google and Amazon music but I had to jump through proxying hoops just like I would have to w/ Pandora, so none of those pan out till they really service Canada.
We have last.fm in Canada too, I forgot about them. I hear there are other choices but I haven't heard of any. Would love to hear if anyone reading this knows of them.