I don't use shuffle often, but something like this would be cool for the times I do, I think. I wouldn't want to do away with being able to shuffle once a playlist is selected, but being able to turn shuffle on/ off as you select a playlist would really be helpful. This really only makes sense with the "replace" option on the "hold" menu, so you could put a sub-menu under that option. Of course, that could get a little tiresome: down-down-down(hold)-left-down(hold)-down.

Rather than a sub menu I suppose you could just go to whatever shuffle mode was last selected, but that means you'd have to have selected a shuffle mode the origional way at some point. I suppose you could just make a setting, but that's getting clumsy again.