I'm a big fan of simple.  Keep it simple.  I run an open source Photo Gallery for some people, and although it's pretty slick to use, it still takes a bit of getting used to. 

I was thinking of implementing something easier.  Something that automatically creates an image gallery based on your folder structure and that doesn't require a database such as MySQL. 

Fellow blogger Angel Brady has a post with a few such photo album projects.  Projects already identified include:

• http://phpgraphy.sourceforge.net/  - PhpGraphy-clean and simple, a favorite
• http://www.sgal.org/ - Singapore-one of my favorites
• http://sourceforge.net/projects/ifoto/ - iFoto
• http://yapig.sourceforge.net/ - YaPig-Nice layout
• http://qdig.sourceforge.net/ - Qdig
  

 Here are some others that work similarly and worth taking a look:

• http://daubau.it/picoplog/ - Picoplog, a minimalistic photoblogging tool (currently in Alpha.  It looks sexy!)
  
• http://www.phpalbum.net/ - PHP Photo Album
• http://spgm.sourceforge.net/ - Simple Picture Gallery Manager
• http://jacquelin.potier.free.fr/fsphpgallerymodj/ - Fsphpgallery Mod J.  I've used this one in the past and it works quite well.
• http://goopgallery.sourceforge.net/ - GOOP Gallery
• http://www.airtightinteractive.com/simpleviewer/ - Simple Viewer (Flash based)
• http://folderblog.org/ - Folder Blog.  I liked this one.
• http://www.zenphoto.org/ - Zen Photo, the simplest most usefull gallery software for your website
  

There are a lot more over on this list and this list. 

Picoplog is definately one product to keep your eye on.  It's buggy.  I was having troubles getting it to work properly.  But once some of those kinks get ironed out, it should be one very useable product.

Until then, I'd suggest trying Folderblog or Zen Photo first.  These 2 seemed pretty sweet.