That's basically what I ended up doing. I used Media Monkey (great app, by the way!) to set up random selection playlists based on my preferred genres, and limited them to 250 songs. Then, I set the Sansa to "shuffle", and then reload the random playlists every few days to keep things fresh.

Funny thing - I grew up with record changers (anybody else that old?) that could play 5 or 6 album sides of 6 songs or so, and here I am with a device the size of two packs of chewing gum that can hold over 2,000 songs, and I'm complaining that I can only queue up 250 at a time! Ain't progress something?