I think it would be cool if the gif gradually enhanced the colors, starting out with the 256 colors and filling in details in subsequent passes. The user would just notice the color fidelity increasing. The trouble is that I don't know if gif implements non-looping animation.
It does support non looping animations. The problem is that I am not sure how you would calculate the 'tween frames. I get the first frame, it's just the final image dithered to 255 colors, but what would one of the intermediate frames look like. A small box with a more restrained palate, or would you break the final image into frames based on spectrum?
I would try to maximize the delta(PSNR) per frame, as a first cut. There are also good perceptual difference metrics. I don't know what algorithm to use. Maybe just the absolute difference on each pixel. Or, you could think of groups of colors to enhance if you're willing to grow the size of the image.
