This has got to be the best free photo gallery software around. Its opensource and installs on your webserver. An example can be seen on my nj surfing club website: http://www.njsurfingclub.com/njgallery/njimages/
Coppermine installs easily and its upgrades are easy assuming you do not have many mods. It comes pre-installed with around 7-10 themes. Creating your own theme is very easy with some basic html, php, and css programming.
Coppermine can be found here: http://coppermine-gallery.net/