My impressions
I've been kicking the tyres, so to speak, for a few weeks now and really like Spotify.
It's worth noting that it's streaming a Vorbis (aka OGG) stream so that 160kbit offers greater fidelity than a similar bitrate MP3 stream.
The catalogue is patchy in places, mainly due to the licensing mess - a whole bunch of songs were removed just before going live because they didn't have clear streaming rights. (This resulted in the removal of a load of Joe Gibbs and the Professionals albums - and just when I was in the mood for some 70s dub!)
The catalogue also gets confused. There are two bands named Heavenly; the super awesome British indie band of the early 90s and a French speed metal band. The two albums they have for Heavenly are from the UK band but the biography (and suggested similar artists) involve French metal. Makes for a surreal listening experience - like the most inept DJ's radio show ever.
Adverts are unobtrusive but not well targeted - not right now, at any rate. They can see what I've been listening to - why make me listen to an advert for Lady Gaga when I've been stuck in reggae and indie for days?
The software is excellent. Small footprint in terms of memory and CPU (far, far smaller than iTunes) and doesn't stutter and fall over when anything processor intensive is going on (like, erm, iTunes). Also obeys the media keys on my keyboard out of the box, which is nice.
Hence, a thumbs up from me.