Well gifs being palette based does add to the problem more. Well the obvious solution is to use the color values for rescaling and averaging (in a proper colors

Well gifs being palette based does add to the problem more. Well the obvious solution is to use the color values for rescaling and averaging (in a proper colorspace), resize the image then build a new palette from the new colors. Well this palette generation isn't exactly straightforward either.