RumGallery may well be the ideal photo gallery plugin for WordPress. While I haven’t tested it yet (it requires the 1.3/1.5 beta version of WordPress), I’m excited by the screenshots, and forum discussion.
While the page header on the plugin’s site gets annoying very quickly, put up with it, as spending a bit of time looking at the example galleries is worthwhile.