I'm hoping that someone has studied this problem and any pointers would be greatly appreciated.
After the downsample, run them through pngquant or advpng. The latter supports zopfli via insane mode and will likely take the longest to compress with the smallest result.