Well, I guess we all agree that we don't want KoF turning into a loli-fighter. On the other hand, if we're a bit realistic, the whole shift to HD(ish) graphics was bound to bring huge changes along. All of the older games had hand drawn sprites. Nowadays, they roto-scan 3d models. That, in itself, means you have a stiffer frame to work on. It also means you get more consistent and professional results. If they went back to drawing stuff completely by hand now, you'd be shocked by the lack of depth that the sprites would have.
On the topic of how muscular/kawaii some sprites turned out to be, I think it's just a broader spectrum than before. Women go from Elisabeth serious to Yuri genki-girl; the guys go from Andy understated to Clark over-the-top. I don't think it had anything to do with appeasing anyone, it's just cooler to have variety. I'm not thrilled about all of them(still don't like Maxima), but I think it's far above standard and likely to improve. It IS their first complete game on this engine and they barely made it. If anyone cares to show me a better 2d game, I'm willing to take a look, but I think that'll just be KoF XIV. Oh, and it's been 2.5 D since they did UMs with 3d backgrounds.
To those who insist on waxing lyrical about how everything was better back then: "C'mon, get serious."