The only thing I can remember it having was the smart playlist feature, where you could construct playlists using criteria like "Has at least 3 stars" and "Not played in five days" etc.

Though that was more of an iTunes feature, that I wouldn't mind seeing in Spotify!

It let you make auto-updating lists to keep your library fresh, and not rely on the shuffle feature.