We've managed to get hold of a video of a Spotify iPhone application in action. We've been aware of the iPhone app being in development for a while, as well as an S60 app, and presumably an Android one, but we haven't seen it running before now.
As you can imagine, it looks fantastic. It promises to give you access to over-the-air streaming of Spotify's entire music library, as well as playlist access. Best of all, you'll be able to cache playlists while in Wi-Fi areas so that you'll be able to play them back when you're on the go. Initially it'll only be available to Premium users (presumably because it's tricky to work out how to serve ads in cached mode).
But the big question here is "will Apple let them do it?". This service completely replaces everything that the iTunes store does on the device, offering on-demand access to songs. We've seen what happens when companies try to improve existing iPhone functionality.
That said, Last.fm exists happily on the device. The difference might be that the Last.fm application won't let you listen to tracks on-demand, just offers you various radio stations based on your listening habits. It won't cache songs, either.
Proper streaming mobile music is the holy grail for a lot of people who have grown up with mobile phones as necessities. Already I barely listen to my MP3 collection on my PC any more, relying almost totally on Spotify. If I could get it on my mobile phone, too, reliably, then my Zune might end up totally retired.
(see also TechCrunch UK's article on the subject)