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.