I swear by
Gallery. They have two branches, V1 and V2. 2 is in beta and requires a database backend. It also requires a pretty good server and/or
Turck mmcache (which I'm now also swearing by).
Here's my Gallery2 install, and one of my
Gallery1 installs. G1 is far easier to integrate into other pages (as I did for team546.com) and requires very little from the server (just PHP and an imagetoolkit like GD, netpbm, or imagemagik - GD is compiled into pretty much every PHP install).