The images are actually small - resized to 600 by 400. But I just figured out the problem: the default zenphoto installation has the album thumbs set to be selected randomly. I guess every time the user navigates to the home gallery page a random thumb is selected for each of the 50 subalbums. This probably means the entire file structure is read to find the random thumb - so a lot of I/O, hence the time-out. After I reset the album thumb to be a specific image, the performance dramatically increased, and it is now as expected, very fast.
So for the next release I'd recommend to set the default thumb selection not to random, but perhaps to the first image in the album. This will allow the gallery to have good performance from the start, without having to modify each album to remove the random thumb and select a fixed one.