I have:
- a 'large' music collection
- a small mp3 player
- not enough patience to keep changing the music around on the player 


Can I get Amarok to randomly load a different set of songs onto the mp3 player each time the player is connected?

not really, but you can manully generate a random playlist to transfer to your player each time. Try the "50 random tracks" smart playlist.

Hmm... That's a shame - given that my flash-player holds 16G!

All I want is the same functionality that can be provided by itunes for the ipod shuffle - so I'll either make my own build without the 50-song limit on the random playlists (why is this limit there?) or make a script to random-load a media device.