In the admin menu (accessed with #6 on your head unit), use the "tune" button to go *backwards* in the menu (instead of going forwards through all the radio types). The first two options you will get (tracks 25 and 26, IIRC), are "randomize all mode" or "randomize playlist mode". When you hear "randomize all mode", press the round "scan" button to select that mode; you'll get a confirmation message.
One other thing... When creating playlists in Media Manager on the PC, there is a checkbox option in the "Properties" for each playlist to include the playlist in randomize all mode. I presume that was done so people could exclude audio book playlists from their library, but it might be handy for other stuff - i.e. you and your wife have drastically different tastes in music... I can't remember what the default setting is, so be sure to check that out before doing a sync.