You are absolutely right about that, I constantly fought with that the entire time creating it.

I like it, good job with the animation. But here's one suggestion (though I'm rather purist in this regard so take it with a grain of salt). I think the color count is too high for a walking sprite like this one, these are the examples of redundant / similar colors:

#352B42 and #3A3858

#FFFFFF and #F2F0E5

#1B0F0C and #121212

I guess you would do just fine with 16 or even 12 colors for this one.