I fixed my problem with .gifs! Turns out it was indeed a problem of too many colors, but when using the Floyd-Steinberg dithering effect in Postioned mode (this is all just so that I can remember how to do it), the colors are reduced below 256 and the gif doesn't have that weird sheen over it. ta-da!
I'm so happy :D