Last.fm is an online radio station with a difference - it lets you skip songs, and from this learns what you like, and plays it to you. As well as that, it's perfectly legal, and is licensed in the UK as a radio station.

Last.fm changed a lot lately as it integrated AudioScrobbler.