I would really like to see a "randomize playlist" button or context menu entry
for the playlist. 

Yes, I know there is the shuffle option. The advantage of this feature would be
that the user could randomize the playlist and then manually tweak it, while
still playing tracks in specified order.