Lifehacker put a bunch of on demand music subscription services against eachother recently, a lot of them were for Android.
I like Grooveshark but it can be a very messy experience. A lot of things are named wrong, versions are unofficial or things just can't be found. It is a mostly amazing experience and the $3/month for the app is the most reasonable but I've been looking at:
MOG
http://mog.com/
[IM]http://rookery9.aviary.com.s3.amazonaws.com/4744000/4744077_9fda_625x625.jpg[/IMG]
vs
Rdio
http://www.rdio.com/#//
[IG]http://rookery9.aviary.com.s3.amazonaws.com/4744000/4744061_9b81_625x625.jpg[/IMG]
Both are about $10/month, have about 7 million songs, allow streaming on the site and in the app and you can download songs to play from the device without a connection. Both are really polished; my problem with Rdio was it kept leaving me in an endless "getting connection" type screen when I would leave and come back to the app. I'm going to try MOG now.
Anyone using any of these?