It's really not bad what they've given some character, and I really don't mind the downsizing of movesets. If anything, it makes it easier for each character to be unique. For example, I'd be OK with Maxima never getting back Maxima Scramble; it was nice to land off weak attacks, but a good command normal can serve the same purpose. (I still want "Maxima REVENGA!" back, however...)
But I think many characters could use some more well-designed, smart tools, such as Andy's "breaking" of his Kuuhadan. This opens up combo variety and options, without blowing too much on the "new animation" budget (which I'd like to see increase for console release, but more on that later!)
While Mai might lack in moves, her normals are at some of the best they've ever been, and her EX projectile is fantastic, as well. Also, this is one of the rare games where she can cross-up with her musasabi-no-mai; it'll turn to hit the oppoenet, after jumping over them. In other games, she's keep going in the other direction, which was always really odd, but semi-good for escaping. Kagero-no-mai or her flip-kick anti-air would add a lot to the variety of her HD game, and her normal playstyle. DP DC'd into Musasabi would help give a lot more variety to her ground game.
Her hitbox on Ryuenbu seems overly-specific ATM, I think she'd solidify a lot if they just fix THAT, even.
Just giving her a fast aerial command move that she could combo into/out of, that'd leave enough time for her to EX Musasabi, such as her old ripoff of Kyo's jump d+C, would be a nice start to improving her, I'd say.
She gets smacked by damage scaling pretty badly right now, and her DMs don't do a great job at landing damage (I wish her Chou Hisattsu Shinobi Bachi locked opponents in for set damage, similiar to Athena's EXDM Shining Crystal Bit.) She's definitely someone who could use a bit more polish, but I do look foward to playing her still.
I love playing Vice in older KoF's, and while I love her leap-DM, it really got less-and-less useful as your opponenets got smarter. The new De-Cide is a great compromise; it makes sure that every hit you land can pull your opponent back into grapple/combo range, landing a free one off every successful catch. This makes me wish she had more grapples than Gorefest and Negative Gain DM.
But she's lost out on her best close normal (2 hit close D), and lost a bit of utility to her far C (it used to have a longer hitbox.) What I personally seem to miss most is her hcf+a/c throw; it had slower startup, but invulnerability, so you could punish attack-invincible wake-ups with it very easily. EX Shoulder charge kinda makes up for this now though, so not TOO bad.
Her new "Splash" is fantastic, though. EX is an instant overhead, the normal ones are leaping overheads, and they covers range; making it a nice suprise. You'll see it land pretty often whenever players USE it. Her leg-slice lightning kick was cool in the past, and I liked SC'ing out of it in 2k2UM, but aside from the aerial version, I think trading it for new De-Cide + Splash is worth it. Shoulder Ram -> Splash followup SC'd into overkill is too cool, as well. (Wish she had an EX version of Overkill!)
I miss her old d+C for anti-air (hear the new one is OK at this), and I'd like to see 1 of the button presses for De-Cide become the old "toss across the screen" variety, for the sake of corner-switching, and maybe as another setup to her Aerial DM (which I'm really happy to see in XIII, so fun and unique. And they actually let you combo into it now! WoOT!)
Almost every aspect that a character is missing in XIII, is covered by EX moves, which is nice. But I think that, as the game has grown, we've seen that people who can do a lot WITHOUT EX have started to stand out. K' and Andy can put you almost anywhere they want on screen, even without meter useage, since their normal moves offer a lot of control.
I think many characters would prove to be more well rounded than many expect, if the players used more meters on them. Even Clark can do an extended ground combo of cl.C, df+A, EX Gattling -> SABB/UABB. But people seem DEAD SET on using Vulcan Attack ALL DAY with him, and rarely seem to budge. If that's ALL you're gonna do, might as well play Ralf! He covers that niche better.
At the same time, I think those who are lacking in meterless options, should get a new special / command normal / stand-out normal in the console version. Continuing the Clark example, I think they should improve his command hop, to give it faster recovery (allowing longer combos on ground, and more general usefulness), and maybe some derived options out of it (such as a clothesline, a tackle takedown, or his old Frankensteiner).
This is why I do think I'd be happier with seeing new moves added into console for certain characters, even moreso than new characters (Though I still wanna see Mary, haha). It'd consolidate the tiers even more than they are now, and has to be easier/less time-and-money intensive than designing loads of other characters straight from the ground-up.