I'd be in favor of just having a "preferred" shuffle mode as a default (perhaps preset to Random) rather than using a submenu. I use the same shuffle mode most of the time, unless I've just added music.

-jk