One of the feature that I love on Amaro (Linux) or Winamp (Windows) is the ability to shuffle the playlist, ie take all the songs in the playlist and shuffle them like a deck of playing cards. That way, when I play the list, the same song never repeat after the whole playlist have been played once.
In the basic music player on Android, and the few ones I've tried from the market, the behavior is the classical "Pick a random song" each time the previous one is ended, meaning sometimes the same song gets played 10 times in an hour, and others never get played.
Is there an app that provide this feature?