I used http://thesixtyone.com for quite some time as the main source of new music discoveries. At some point they redesigned their site and it became really hard to use. The old version is still available now but who knows for how long. So I feel like it's time to move on. I also scrobble my music so the integration with Last.fm is quite important for me. Is there any other streaming music service with scrobbling support?
Spotify is very good and has Last.Fm integration, but is not available outside of Europe yet
Rdio is a music service, where you discover music through your friends and followers. Rdio works in the browser, on the desktop, and on Android, BlackBerry and iPhone smartphones. Rdio also provides music downloads.