Okay, let's see if I can organise these thoughts...
I've grabbed a few of the sprites and shown a (pretty sloppy
) colour wheel for each of their palettes. As you probably know (but I'll go over it briefly anyway), colours that are opposite eachother on the colour wheel are complements of eachother. Using complementary colours leads to a high degree of colour dynamic. Introducing complementary elements is the basic reasoning to most of my cajoling of the colours in my original edit.
Which brings me to Golem. He is my favourite sprite amoungst the collection, and I wanted to bring special attention to him regarding the revision you made just to make sure you understand where I'm coming from. By tinting the shadow tones towards teal, we create a colour dynamic (interests the eye) and a temperature scale (harmonises with the scene). If you have a whole bunch of greys on your sprite, he is automatically the least saturated element in your scene. Your eye processes him as "grey blob" and moves on to find some colour. The large area of teal and grey on the sprite also creates a
setting for the highly stimulating red-orange, allowing it to
accent.
Accents concentrate colour dynamic into a focal point (or points). The setting is generally a collection of more neutral colours that have minimal dynamic with eachother, distributed over the majority of the piece. Picking greys and the muted complement of the accent works very well as a setting. The role of the setting is to starve the eye of colour dynamic, so that it wants to search for something in the image that will balance it. The eye immediately snaps to the accent, which satisfies the imbalance. For this reason accents are fantastic for faces, eyes and other points of interest (such as Hammy's hammers). In a more traditional piece (ie a painting) a key figure's clothing may be the accent of the entire composition to bring the eye to them as the person of interest.
Accents also work with tonality. You can have a setting of dark tones and an accent of a very bright tone. This is already a common element in many of your sprites; the faces are a bright white. Works well. Beware though, that colour will compete very quickly with tonality. Take Dex, for example. The orange and white compete for attention. On the portrait this is less true, but on the sprite itself, the eye continuously bounces between the face and the bright orange limbs. You might want to fiddle around there and see if you can push one of those into the setting and leave the other as the accent. Up to you.
The vast majority of the sprites I editted use complementary colour schemes. An example of a sprite that doesn't is Pea. Here we use all the colours
between two complements, grading up from the coolest colour to the warmest as we move up in tonality. This is an analogous scheme. Because we have such few palette entries to work with here analogous schemes give you a stronger colour identity because all of your colours are closer to the midtone (which, assumably is the "colour" of the object you are drawing, in this case Pea is green). Pea is so green that the light is heavily tinted in towards green, pulling the colours on the wheel in towards that zone.
Next are the two purple dudes. I wanted to show how you can take two characters that you might want to have a common theme (in this case "purple") and how you can "rotate" the colour wheel of one to get a new colour wheel for the other that still shares purple as an element. This way you end up with sprites that can be similar, but still stand out as unique (though I got a little extreme in differentiating these two).
And last thing about hues I wanted to mention was monochromatic palettes. Any scheme that has all of its colours sitting on or very close to a single point on the colour wheel is termed monochromatic. With a monochromatic palette you sacrifice some tools to gain a stronger sense of mood or atmosphere. The thing you sacrifice is colour dynamic (obviously). Establishing a temperature shift becomes extremely difficult, so you run the risk of isolating the piece from the rest of the composition. Sometimes that can be desirable (especially in games), though, but you have to be careful that the context you are isolating the element in makes sense. For example, imagine we had every sprite in a game harmonised with their scenes except for ONE. Except for this weird colour difference, there is no other reason, no context, for the sprite to be set apart from the others. This creates a conceptual dissonance in the player's mind. Dissonance is the feeling of chaos, nonsense, lostness. It is extremely unpleasant, and ultimately you don't want your graphics to be unpleasant, right?
Which brings me to Tesla. I know you like her as purple. The monochromatic scheme creates a mood regarding her; it communicates an aspect of her character. But is that style going to sit next to the style of Hammy? If you have a context for why she can be like that and Hammy like that, it will sit with the player's subconcious just fine. Otherwise there will be a dissonance, however slight it might be. The context can be something like "all the key characters are monochrome as a visual metaphor for their role within the party of good guys", or it could be "all the girls are monochrome because female robots are extremely unique in the setting and a key part of the robot's culture". Etc etc. If this is explained to the player, be it explicitly or implicitly, it will be fine. In fact, it will be very interesting.
That's kind of abstract though. If you want reliable, functional graphics it's probably best to stick with consistent methods across the spritework.
OKAY. That was kind a bit of a ramble. My brain went to a place I didn't know existed. But there it is.
I threw in a revised version of Tesla with more colour dynamic as a suggestion of something you can do that keeps the theme of "purple" but introduces temperature scale. Notice how it catches the eye more than the monochromatic version.
Final thing I wanted to talk about was splitting the palette into definite zones of light and shadow. I think this is one of the reasons Hammy pops so much. The key action when shading an object is dividing the form into areas of shadow and light, so it makes sense so divide our tones along those lines as well, especially when we have such few palette entries to work with. One problem, however, is that as our sprites get smaller, outlines start to take up a greater proportion of the canvas space, so we are left with less room to perform shading. Pixel clusters also become much more influential at smaller sizes, so shading areas become submissive to the clarity demands of the pixel clusters.
In short, shading comes undone with smaller sprites. Your main tools become lines, shapes and colours. It makes sense, then, that for smaller sprites you divide your colours up to maximise the expression you can get with these three tools. You want a nice dark outlining colour that all the other colours contrast with. This is why on the tonal scale I have next to Pea you can see the darkest tone sits really low on the scale and the others are pushed more up into the top half of the scale. I still generally try to adhere to the shadow/light division where I can, though.
I can't remember if that was everything, but those are the thoughts I have at the moment. I hope they are helpful.