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.

Hm, well, maybe you should make his nose more prominent, since his eyes are so huge, it makes the rest of his "face" seem tiny. I love the dark shadow you used under the armpit, but it makes his stomach look flat. Maybe you should use that dark shadow to chisel out his male physique some more.

First off, let me say that this is a really big project, and it's probably not going to look like Capcom's level of quality. They have several people (probably 30 or more) working on any game (just look at the credits for MegaMan 10).
With that being said, I still think you should try to do it, because you will learn a lot from it. Anyway, on to some critique...

You have alot of things here, but overall, your pixels suffer from jagged lines, anatomy and proportion issues, and banding.
I'm going to assume you're going to borrow some graphics from Capcom themselves.

The Castle. It looks like you edited one of Capcom's castles, keeping the skull and the satellite dish with minor changes, and then adding the big "fangs" and the weird hypno-dish. From a design and architectural view, these things don't seem to serve any function nor aesthetic. It doesn't really add much to a castle. A good study of buildings, from real ones to crazy artsy ones to ones in comic book and other Capcom castles, from a design perspective, you need to add features that are both functional and aesthetically pleasing.
MegaMan/Protoman. They have significant perspective and anatomy problems, in addition to poor color choices, banding, and jagged lines. Especially the feet. Again, the best way is to study anatomy, from real people, to cartoons, comics, and other MegaMan titles.
The City. It looks good for the most part, except the clouds and the "tube" in the lower half. Although I think this was a direct rip from other titles...

Generally, you need to study art, and pixel techniques. If you don't understand what jagged lines or banding are, there are great topics on here you can search for. For anatomy/architectural/color choices....unfortunately, that comes from study, study, study, and practice, practice, practice.

I hope I wasn't too harsh on you. But if you really want this to look like a MegaMan game, I should tell you the truth.

And now cute smileys. 

It's mostly well, but I think the proportions on Link are a tad off. I think he needs a bigger heads, shorter/skinner legs, and a smaller shield. For the middle girl....I think her pants should have 2 lines of pixels removed on the left, and maybe her face is just turned too far to her right.