After trying a lot of other options I stumbled upon Ignite Gallery and found it does just what I want.
It was fairly easy to setup however I got caught on the permissions for gallery visibility. After some trial and error I worked it out and looks great.
My only complaint ( and hence no 5 star yet ) is the documentation ( or setup guide ) which could look a lot neater, with clearer descriptions and easier to read. The forum though is full of very helpful threads and once purchased the developer also provides code customisation for those tricky little things that need to be fixed.
Overall I'm very happy and I'll be sure to use this for many of the sites I have in development currently.