I have seen, and commented on here in the monastery, this same poor quality optimization in GD you describe. My images have all been JPGs, but no matter how I set the optimation, the result is as you described.

I tested this by "Saving for Web" in Photoshop and then viewing the two images side by side in my browser. The difference is striking. The only thing I can attribute it to is the optimization algorithms used by GD.

I would love to see the difference Image::Magick makes doing the same thing, but my web host does not support it.

I'd hate to think that this is the best GD can do. I've got my fingers crossed hoping some monkish guru will have a solution.