After spending some frustrating hours trying other well known gallery plugins and meeting a host of issues, I came across WP Photo Album Plus and it really is superb.
As previous users have said there are a multitude of options compared to other gallery plugins, and if you're thinking of a gallery you've got to plan a few months ahead when you'll have hundreds of images - how will you organize them etc. Sub albums, links, updates etc. This plugin has it all.
Can't recommend enough!