Yes, you read that right. The "shuffle" function in Spotify is nothing more than a randomizer. There's a difference? YES.
RANDOM - Play one song. The next song can be ANY song in your playlist. Including the one you just listened to. Though I've never had this specifically happen, I literally just heard the same song that I heard 2 songs ago. This is how Spotify's "shuffle" currently functions.
SHUFFLE - Take your entire list, shuffle them (like cards), and play the first song in the shuffle. Once finished, move that song off the pile. Once the pile is depleted, shuffle the deck again and start over (maybe pop a message up).
I know enough about programming (not much) to know that shuffling is probably a bit harder than random, but come on. I may be in the minority, but I don't have a lot of little playlists. I have one list with nearly a thousand songs in it, because I like all the music, and am rarely not in the mood for one of those songs. But what I can't stand is hearing the same song over and over again. I think there may even be songs in my list I haven't heard yet, while I've heard others 4-5 times.
I know it may not matter much, but I would probably lay down the money for at least a year subscription if this feature was implemented.
EDIT: Another user pointed out that I can see what all is queued up in my shuffle by clicking the Play Queue link, and that Spotify supposedly sets up a rolling shuffle of 50 songs. It would be nice if this range could be expanded to say 50-100% of your playlist.
EDIT 4/6/12: I just dealt with the same song 16 tracks later. The song played the first time yesterday afternoon. I went home, listened for a bit on my home PC (just a few songs), then started listening again this morning. If the list recycles itself after a day, or if you log in from another computer, I see that as an area for improvement.
Updated:
Hey folks, we have made some improvements to our shuffle algorithm that we are turning on as a default for all users. We'd love your feedback on how your shuffle experience changes after today (Feb 5, 2016). Thanks for your feedback, your comments are essential to helping us improve Spotify.
Update Aug 2018:
Hi folks, it sounds like quite a few of you are experiencing only the top tracks in a playlist shuffling/ playing when using Connect. This has already been reported here.
We’ve given a transparent status there explaining there isn’t a current timeline for a fix. Please do leave a VOTE there if you’re experiencing the issue and a comment. We can then bring this information back internally to show the size of the issue for our users.
If however you are experiencing issues with Shuffle when not using Connect, please get back to us in this thread we've the questions we've listed and click +VOTE. Thank you!