I was mis-remembering how iTunes work there. It will auto-re-shuffle in some cases -- you don't always have to do it explicitly -- but it looks like it has more to do with whether you switch away from the playlist after the music stops playing. If I simply "pause" and select another song, without switching away, the order remains stable as you say. If I switch to say the Music library view, and then back, and double click a song (any song), it re-shuffles with that double-clicked song on top, playing.