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.
And yes they do plenty with the native UI, it's just in the details. Those details that matter.