Google play music is now available in Canada in both Store and Radio. I signed up already. http://g.co/PlayMusicCA gives you a 60 day trial instead of 30 and then after 60 days it is $7.99 a month instead of $9.99 if you keep subscribing. 20,000 songs to choose from so far iirc and the radio is pretty good. You can share playlists and also stream this throuh a chromecast. I believe now that it is actually available in Canada you can easily sign up and upload your own music and stream that also!
There are deals right now on albums for $1.49 also in the store front.