I currently use PHPotoalbum, it has a lot of the features mentioned above. Here's another example: Ellaybe Island Gallery (one of my websites...this is a hobby for me)

I tried Gallery before but never could figure out how to open the tar.gz file. lol! I've since learned how..

but that brings up a question....does Gallery allow one to edit the look of each catagory differently?