There's a lot of them out there, but they all have their assorted quirks, making different ones better for different things. For example, last.fm doesn't allow pausing, Pandora is US-only, and so on.
It'd be great if people could post one service per answer, and use a format to allow easy reading and comparison, such as:
Short description/tagline/similar, (keep it brief, use Extra Details section for more).
- only plays X music
- country/region restrictions
- limited to X browser/client
- benefits to this service
- which the average doesn't have
- missing or bad features
- not covered by restrictions
- e.g. no pausing
Any other rambling stuff you want to write to add detail not provided by the above sections