So, I finally got around to setting up a PHP photo gallery with a MySQL database. The ability to customize the look and feel using CSS and templates was a major consideration when it came to finding a good script to use. After looking at dozens of scripts, I came across singapore, great little open source, image gallery script. Check it out, this may be the one you have been looking for.
UPDATE: I’m now using Flickr to host all of my photos.