Don't be so harsh on yourself.
I would recommend staying at 16x16 without having to break the border, your characters will look better that way. It's also good practice, since that's really where you learn pixels, because you have to make a readable image when you're cramped. I would say, try to go to make sure it reads as what it is, don't need to spend your time making sure every detail works, because you really don't have room. Also try to keep perspective in mind, think about from what position the person is viewing these guys, and keep that in mind. From what I can tell, it looks like I'm supposed to be looking at them above from about a 45 degree angle, if that's true, then the heads should appear a little larger and little detail given to the bodies. I find that making 16x16 characters looks best when most pixels are given to arms and heads, and less for torsos and legs.
The bigger problem is with your colors. They're very bland and boring. What they need is contrast, that means that each color has to be very different from one another. You don't have to choose colors that just in one attribute, or hue. For example, if something is supposed to be red, you can make the highlights yellow, and the shadows purple. You need very few colors to make a detailed sprite at this size, so, if I were you, I think you should try to limit your colors for each guy at 6 colors (including transparency) or less.
I hope that helps you.