I could write a ridiculously long review for all of them but instead of rambling I'll try to keep it short and to the point.
Grooveshark just isn't in the same league as the other apps. It crashes and pauses by itself. It's UI is ugly. There's a lot lot lot of flicking involved because of all the duplicates and mess that Grooveshark hosts and since it's unofficial/user uploaded there's a lot of missing songs in albums. Your favorite track could be missing. It's cheap but not worth it - at least as of right now. $3/month
Both MOG and Rdio are good but I recommend trying them both out to see which you prefer.
MOG is gorgeous and very Android. The music plays pretty quick but it's not that user friendly. The bottom row of buttons aren't too clear to understand and when you touch one, they all change. It's easy to get lost but it has everything I looked for, it's officially licensed so the catalog is complete and neat and it performed well. Downloading songs for offline listening was super simple and quick. Trying to exit the app is a mess; I think it's taking me back to every screen I had looked at because I'd exit and see another MOG screen and have to do this 8 times but you could always pause/stop the song and not exit. The sound quality was good, it has radio Pandora-like features and it's nice. No landscape though. $10/month
Rdio is a nice app but it's very basic. It has everything I looked for as it's officially licensed like MOG. It seems to be pretty user oriented; it's very clean and minimalistic. The nice thing is if you search for an album or artist it will also show relevant "popular" results that you may be interested in. It also has Pandora-like artist radio. What sucks about Rdio is it seems to have some connection problems. Earlier it went into a Connecting message loop and wouldn't let me back in, currently I selected an album and it's loading the album forever. I'm over wifi right now so this is odd. Also, downloading songs for offline play is a bit annoying in Rdio because the button to do so is microscopic and would be annoying to hit precisely even with a stylus. $10/month
Maybe it's just me, Launcher Pro, my wifi or my Droid so Rdio is still worth checking out. None of these apps are perfect yet but MOG is the best bet in my opinion. It's gorgeous, has good sound quality, is distinctly Android in it's UI (even has a widget) and performed well. I'm sure with some time the buttons would make more sense but it doesn't seem too intuitive, Rdio is much simpler.
Start with MOG imo. I'm heavily considering subscribing. We'll see how it goes.