Even with a delay, a large color GIF image is still a good idea.
The first frame can be a simple rough (no dither quantization) of the image, with later frames adding more colors. As such the image will appear immediately and it will quickly become a higher and higher quality.
image with each frame adding 256 more colors to the currently shown image.
The key is that the GIF image does not loop.
So the question then is how best to separate other the colors. Starting with what should the first 'rough' image be (perhaps the most widely separated set of exact colors with high color counts). The next image probably should be the next set of exact colors with high color counts that are most different from the first set, and so on.
So how do you find a ordered list of exact high count colors that are well seperated?
NOTE: in some ways this is similar to the problem looked at in the discussion on
for selecting well seperated high entropy points in images, but this time working in 3 dimensional colorspace rather than in a 2-dimentional entropy map.
IM can certainly add such an algorithm (if it can be worked out) as a special '-layers' method, though who should program it is another matter.
First step however would be some type of scripted 'proof of concept'.