How about adding an icon at every playlist selection level that shuffles the playlist. It would look like the "right arrow" that right now selects the whole playlist. Perhaps a right arrow with a S in it or something like that, to the left of the right arrow. The normal "right arrow" would select the playlist without shuffling, and the "shuffle arrow" would select and shuffle the current playlist.

The global shuffling is useless because I typically want to switch between the two. Personally, I never shuffle albums, but I'll shuffle other playlists with multiple artists/albums.

This is nice because it doesn't require setting special flags on a per-playlist basis. At the time when I'm selecting the playlist (in the car at 80mph) I can make the decision. And this doesn't affect those people who would rather just use the global shuffle option.

If "global shuffle" is on, when you select a playlist, it defaults to the icon that would shuffle that playlist and vice versa.