I had a few options for what I could do with the colors on that last pic, but I can only use 256 of them max in a gif. Those bands of color you see going across the guy's face are due to the limited colors available. As usual I was keeping the file size under 3 mb, so I had to pick the best option I could find.
In this case I went with 90% dithering and 0% lossy gif compression. Less dithering means more bands of color. More dithering gives a more even, but grainier look, at the cost of a larger file size. I've found that lower dither values are more aesthetically pleasing in some cases.
I'd post a screenshot from Photoshop where I was configuring this, but I've already closed (and not saved) the project, since I typically only bring things briefly into Photoshop for the final gif optimization. I'd like to teach some stuff in this thread if I can, so I might show the optimization process for a future gif.