I like to use the 'dynamic random playlist' mode in Clementine. It maintains a playlist with the previous 5 or so songs and a queue of 20 or so songs which are coming up, which is added to randomly from another playlist (exluding songs which are already in the list). Also (and this is the thing which I rarely find in other players), I can re-arrange this working playlist if I want to follow a theme, add or remove songs coming up, and it will just transition back into a random mode when the added/rearranged songs have played.