Google Music is good, but it has a couple of downfalls. First, the app is available everywhere but the service is only available in the US. Second, no one really knows what the implications of Google's terms of service are for people that download music from 'free' sources. Google has publicly stated that they will remove any 'illegal' songs from your library. Presumably they'll use digital watermarking to identify such songs for which thousands of copies exist on the net. Will Google share this info with the RIAA? Will the RIAA try to obtain access through lawyers someday? Who knows...
I use AudioGalaxy. Streams music from your home computer to you via their remote server. Works fairly well even with limited bandwidth. No lawyers necessary.