Recommend a decent photo gallery plugin!

Hands down, NextGen Gallery.
http://alexrabe.boelinger.com/wordpress-plugins/nextgen-gallery/

You create albums and within them, galleries; you can upload right from your computer, add EXIF data, scan the created directories for new images (which means you can upload new stuff and NextGen will find it all). It’s quite elegant. And you can even use it to create flash based random header graphics. 🙂

Also think about using Plogger
http://www.plogger.org

But that’s like maintaining a separate gallery. The good news is that there is a plugin called PlogPress that displays random images or albums from your Plogger install right inside WordPress.