Hot on the heels of Spotify on Android comes another popular streaming music service, Pandora. Capable of streaming a custom radio station over 3G or WiFi connections, the app - which is available to download free through the Android Market - takes an initial artist suggestion and then creates a playlist of similar tracks.
Listeners are then able to rate the suitability of the track using simple thumbs-up and thumbs-down buttons. Mark it with the former and you'll hear more songs like that; use the latter and you'll not hear it again. Unlike Spotify, Pandora doesn't allow for music on demand, but it does take away that "what will I listen to now?!" indecision.
There's also a desktop widget which can be used to control playback without delving into the app itself, and it of course continues playing in the background. Pandora is only available in the US at present; the Android app is available to download now.
[Thanks to everyone who sent this in, and Andon for the screenshots]