Well, you're right, you're definitely not using the NES palette, but that doesn't mean you can't go for that style. My Secret Santa gift has an NES look to it, but I certainly didn't use the NES palette either.
The running animations are fairly stiff, I suggest you make a visit here
, it helps a lot (running animations are a HUGE pet-peeve for a lot of senior pixel artists, because they're often really poorly done). My main issue is that the girl's hands travel really far upwards and downwards, but her legs don't show the same dramatic motion, plus her chest, stomach, and head don't move at all to match.
Beyond that, good job (sorry if this is a lot of critique)!
Eh, I thought so. I tried to find some tutorials on 8-bit spriting/8-bit palettes, but nothing really turned up. I like them better this way anyways.
On the subject of the animations, I was keeping it restricted to 3 frames to keep in the spirit of Megaman and the various other 8-bit references I used, as well as giving it an old NES-game style. I did try to make it more fluid though for the girl, since it's more noticable on her than on the robodude.
I'll probably tinker with it for a while. I moved the legs to a more extreme motion to go with the arms, like you suggested, and moving the torso is still being fidgeted with.
Critique in any quantity is fine by me, as long as it isn't repetitive or condescending.
Also the current edition:
Added some more animations for the girl (jumping, skidding), put more crap on the big ship, and made some animated tiles. Also changed the badguy's weapon to a rocket launcher, since those are cooler anyway.
To be worked on is an "on-world" version of the robodude's ship (the little tiny one near the big ship's landing strip, you can see the WIP big version on here too), a better weapon for robodude than a stupid generic lasergun, and more badguys.