I'm using both Google Music and Amazon MP3 to find out which I like better. Amazon seems to offer a slightly better feature set so far and slightly easier navigation, including the lock screen controls which is big in my book. Their shuffle is terrible though, the order is always the same, so if you close the app and go back in you start at the same song every time, and since they are in the same order, you have to either select the next song you haven't heard or keep skipping to the next song.
Google Music is Beta still, so I'm hoping they catch up on features, especially the lock screen controls. Beyond features though, Google Music has been more stable in streaming over 3G. I get less "stops and skips" to the next song. It seems to take longer to upload music than it does with Amazon, but after the initial upload who really cares.
We'll see...