I just finished adding a random picture to the main index.
Download block-random.phps, rename it to block-random.php and copy it to your Gallery directory. Then add this PHP include to the file you want to add a random picture to:
<?php include("http://www.yoursite.com/gallery/block-random.php"); ?>. The current code allows you to add a
?album=albumname parameter to the php file, so you can force it to use just one album.
I had to edit the code a little bit, because it expects to be embedded within an IFRAME. Because they are evil, I hacked the code to only generate an IMG tag.