After searching for new gallery and investigating lazygal, I finally decided it's time to give it some real world usage. My current album from Japan is being processed by this damn fast tool.
It needed a bit of hacking, but as the core was already there and Alexandre Rossi is quite cooperative upstream. I managed to implement almost everything I requested in original post. The only thing I'm still not completely happy with is the theme, but I hope I will improve it over time.
From original requirements, I completely dropped links to full size images. There is simply no reason to put here crappy pictures which my only camera I currently have here (built in camera in Nokia 6234) produces. Also once I'll buy new camera (what will be most likely Pentax K10D), I probably won't upload huge 10Mpix images on web server as I don't think it would be good for anything else than wasting my bandwidth.
