I wrote a Wp gallery plugin pretty much for my own needs.. It is heavy implemented into the WP structure.
It uses pages for categories and albums and therefor also the original WP comment system to comment on pictures. It is integrated in the url system of WP just like pages are.
You can show random images, last comments, last pics and last albums on the sidebar..
If some people say, hey, that's great!, i would try to make a "real" plugin..
Well, check it out on animalbeach.net/photography !