This question is coming from a somewhat ignorant perspective about KoFXIII's balance, so please bear with me?
What would be easier overall? Nerfing, Buffing, or is the best option a combination of both? Because if it is the latter, then maybe the conversation shouldn't be concentrated on just depowering the top tiers, but on how to powering up everyone who needs it?
Of course, I'm also not naive enough to believe that optimal (not perfect) balance is easy, but I think striving towards it would be a worthwhile experiment. Even if the game needs multiple patches.
Just my 22 cents. If I'm thinking about this in the wrong way, it'll be a great eye-opener to know why.
The easiest thing for SNK to do would be to do nothing. I'd be disappointed, and I think the game may suffer for it in the long-term, but it wouldn't be the end of the world. Recent Japanese matches featured some Goro and K' fights (i.e. bottom-tier vs. top-tier). While Goro was mostly out-matched, he was at least able to keep up with K'. In competent hands, every character has potential.
The next easiest thing would be to simply nerf the S+ tier: K' and Raiden. What would be even better would be if they could tone down the S- tier: Kula and Elizabeth. If they did that, in my opinion, it would be the most balanced KOF ever.
Personally, I'm against adding moves for the home version. Of course, some of the lower-tier characters could benefit from them, but even one move, if poorly balanced, can radically change the game (i.e. the drop kicks). I'd prefer the console version to be a refinement, not a reinvention.