How about a cloud-like feature that 'pushes' your most recent song to devices connecting to Spotify?
Say you're listening to the new Arcade Fire on your iPhone. You get home, boot up your Mac and start Spotify. Bam, there is the song you were listening to on your iPhone. You click 'Play', it starts playing from exactly where you left off. No hassle, no searching for that one song you were listening to.