Music streaming app suggestions?

I've been a subscriber to Rhapsody for a couple years now, and haven't been happy, but there hasn't been any services I could find with as large of a selection as they had. But, now, the last straw is that after the past two updates, Rhapsody is utterly useless. Searching for any artists, songs, or albums brings up nothing. It'll find them, but as soon as you choose what you want, it acts like it doesn't exist. I'm sick of the app skipping songs randomly or not working at all.

Long story short, I need a new great streaming music app. I am currently trying out Slacker, but its app is extremely unreliable on my Nexus S. It crashes and freezes and it takes forever to just start up. Spotify's UI looks like it was coded back during Android 1.5, so that's not good. So, are there any other suggestions? More than the selection of music, I just want an app that WORKS RELIABLY.