One thing that keeps amazing me about Spotify, is how there's seemingly zero latency when you jump to a new track. This is true for any track - even if you do a search query over the whole catalogue, then hit a random entry in the list of results, the music starts pretty much immediately.

This makes it much more pleasant to use than something like Grooveshark (Flash-based). I really don't see anyone pulling that off with a web client.