Hey, these are some funky characters! You've got some nice flash animations on your gallery so I'm interested to see how these animations come out. Now on to the critique.
My biggest issue: these are too messy! The main culprits seem to be too many black lines and too much dithering.
Too many black lines can overpower a sprite. Try coloring the outlines in places, and even completely omitting outlines. The internal details especially can get lost with lots of outlining. You have really direct control of lights and shades at this resolution. Try thinking more in terms of rendering solid forms rather than laying down flat images.
Dithering... I'd say drop most if not all of the dithering from the sprites. You can better show form by adding a "buffer" shade between your highlight and shadow. And I imagine it could be a chore to animate those dither-patterns.
These characters are all very unique, and they aren't served well by using the same palette. I'd like to see them all get unique skin tones and different colors themes. I'm not sure what your restrictions are, if any, but traditionally sprites like these might each get a unique 16 color palette.
I made an edit of this Winston fellow to address some specific points.

- Colored parts of the outlines, removed much of the internal outlining.
- Cleaned up internal details, especially on the gun and face.
- Removed lots of specular highlights. It was a bit overkill methinks.
- Added another blue shade to act as a buffer.
- Tweaked skin colors for a less pale look, utilized some of the browns from the hat/armor for skin tones.
The biggest change I made was eliminating most of the single pixels that stood out. Wilson in particular suffers from this, and it contributes a great deal to the messyness. There are lots of places, I'm thinking his vest especially, where there are little bright or dark pixels sitting all by themselves. Pixels tend to want to stay together in clusters. When left along they tend to stick out like a sore thumb.