Thanks

This is taking me hours and hours just for this one guy though.
They just fly by though, this is quite fun.
So here's our evolution:





and the current iteration:

He's a little more assertive now

edit: Converted him to 4bpp to see what would happen


edit 2: For other newbies like myself, check out the color of his eyes vs. the background. It's the same color! What you're seeing there is the illusion of a color changing appearance because of its neighbors. Good theory to get into for working with limited palettes.
I'll still want to tweak the colors to take away the sick green tinge from the conversion, but I wanted to see what it would look like with the app doing the optimization.
(app used: GraphicsGale)