You could realize that turning off shuffle is just one button (0 on the remote control), so it's really not that tough just to turn shuffle on and off as you need it.

True, but it requires me to convince my wife to put the remote back under the sun-visor where she found it, something she's eminently forgetful about.

If turning shuffle on and off has you worried about "songs you already heard" coming up on the next full shuffle, remember that 2.0 will have a weighted shuffle option, so it won't be an issue when 2.0 comes out.

True... good point.

You could create two separate playlist trees-- one of them called "random" and the other one called "sequential". Mark all the random ones and their children as "always randomize"

My experience with "always randomize" doesn't lead me to believe this would work. Always randomize SEEMS, from what I can tell, to only randomize "immediate children", e.g., if I have a structure like

/
/Artist/Sting
/Artist/Sting/AlbumOne
/Artist/Sting/AlbumTwo
/Artist/Metallica
/Artist/Metallica/AlbumOne
/Artist/Metallica/AlbumTwo
/Artist/Floyd
/Artist/Floyd/AlbumOne
/Artist/Floyd/AlbumTwo

And they were all marked to "randomize contents", then Artist would randomly play one of the three artists, which would in turn randomize which album it was going to play, and then randomly play every song on that album, before moving on to the next random album, until all albums were done, then moving on to the next artist.

At least, that's what it appears happened when I tried setting that up to see if it would work as a replacement.

Still seems to me as though this should either (a) already be something in the player I'm just clueless on how to use, or (b) a really cool feature to add.