Good question, and if you find an answer, please post it here.
I've managed to gain a small speed increase by setting all the optimization options in the Gallery config. It's still slow though. Enabling FastCGI has had no effect, despite the fact that, according to the Gallery forums, it should help. One of the problems is that, due to DH restrictions, it has to run as CGI rather than the faster mod_php. For this reason, optimizers like eAccelerator won't work either.
The only thing keeping me using this snail is that I don't have the time to go through the install/evaluate cycle for half a dozen or so replacement candidates.
If you want useful replies, ask smart questions.