Where is Last.FM on this list? It's actually the best (in my opinion) service out there. Their "discovery" feature is the best, and simplest to use - just choose "Play artist/song/tag XXX radio", and it will play related songs for you. Their catalog seems immense, and I listen to some of the most obscure stuff out there (/hipster joke). And it's completely free.. the only thing it doesn't do is play music "on demand", but nobody else got that right either (for free).