I do not know why they got distorted.
It's because it's an animated gif. Animated gifs, as far as I've found, have a limited color palette, 256 colors, as opposed to static images which could have millions. I very well could be wrong, but the basic understanding is that an animated gif can have less colors than the actual animation you are making once it is saved. If there is a way around that limit(I've seen more than enough gifs that look like they exceed the color limit of gifs I've personally made) I don't know it yet. Photoshop isn't really meant for animated gif making anyway ^^;
You should make a mark for each of the false gods. That would be EPIC!
That sounds like fun. I might try my own hand at that.