I really like the way Winamp handles shuffle. It takes the current playlist (whatever is selected to play), then shuffles it in memory for stable play order. If you select a new song manually, it will play that song, then resume the old play order.
I use ncmpcpp (a client for mpd) and it does the same thing. I've never had any issues with its shuffling; it just works exactly as I would expect it to for everything.
On a sidenote, mpd + ncmpcpp is a killer combination for playing and managing music. I can only recommend that to anybody geeky enough to use a CLI music player :)
