best quality jpg and least compression png are still making a copy of a copy you lose quality every-time you re-compress the images. Try using a non-compreses starting image and see what happens.
PNG is in fact lossless like gif, but you can turn down truecolor to 8Bit pallet.
You could try using $image = GD::Image->newFromPng($file, [$truecolor]).
The truecolor switch is new in GD 2.11, look here for more new things.