Hmm. Ok, only way to properly do this for me is to ignore what makes sense, and just throw ideas out there, lol. So I'll be tossing out a few "Why not just make a new character?!?" ideas along in here...
Ash Crimson - Saiki. Modify face, voice samples, maybe a few mannerisms, and of course, the hair.
Team Japan
Kyo Kusanagi - Maybe a Syo Color palette? With the extra outfit designs atop his normal wear.
Benimaru Nikaido - Loose hair! Ramp the Bishonen factor up a notch. Or just add his hair falling down as a special chip damage KO.
Goro Daimon - Brian Battler style Football Armor, with a refernce to the Football guy from World heroes thrown in as 2 color Palettes.
Team Elisabeth
Elisabeth Branctorche - I'm not much of a fan of the "boob window" compared to her new outfit, but if it could be added as an alt, so be it. And she needs a Color thet references Phoenix Wright's Von Karma!
Shen Woo - A shirtless design, so that you really get to see his arm and back tatoos. Put in a 100% Mukai color while you're at it, for fun.
Duo Lon - Give him Vampire Hunter D's hat + loose hair, since he's based on him. Make a color based on Classic Red Mage from Final Fantasy while you're at it!
Fatal Fury Team
Terry Bogard - MOTW Terry. Alt win pose has him tossing off his jacket, rather than Hat. Oh, and make normal Terry lose his hat for special KOs. And make the hat come back down from space in default costume's win pose.
Andy Bogard - DarK's alt is solid in style. Go for that, give him Galford and Hanzo colors for the set as well.
Joe Higashi - Muy Tai Chamionship Belt, (the one he taunts King with in some games), or just totally lose it, and give him that Kimono-style jacket he's worn in some intros.
Kim Team
Kim Kaphwan - More variety between top/bottom colors. Fit a back emblem / Headband that has some Kanji for "JUSTICE!" or something on it.
Raiden - Is perfect already. Big Bear + Colors are great.
Hwa Jai - Add some more arm and ankle wraps to differentiate him from Joe. Have an opponent chuck a bottle of special drink to him upon KO, leading to either he cradling it (haha), or it falling on the ground, and shattering.
Women Fighters Team
King - Hat + modified haircut, Maybe a Jacket, a few mono-color outfit schemes, that's about it. Really don't want to see her "tart'd up", lol.
Mai Shiranui - Leggings would be OK, MI Alt would be amazing, but I'd settle for some embroidery on her outfit. Iralf can get CAMO PANTS, she should be able to get some Sakura petals / tree branches! Oh yeah, and drop fan upon K.O.
Yuri Sakazaki - Really is fine already, her alt is great. Maybe a few more colors to make use of the varied pants designs, though.
Art of Fighting Team
Ryo Sakazaki - Bloody / bruised face upon KO! Apply this to the whole team, maybe make Ryo's outer Gi burst /tattered pants upon KO. Make colors that allow differnt top/bottom Gi colors for 2nd palette.
Robert Garcia - NGBC older Robert look. Make coin fly out when he's KO'd. Return coin-flip victory pose.
Takuma Sakazaki - Mr. Karate already rocks. Increase colors on both palettes, make Karate Mask shatter upon Special KOs. (Explode for special move unblocked, shatter in half and fall for chip KO.)
Yagami Team
Iori Yagami - Forget Colors, just make w/Flame Iori. Give him some unique colors.
Mature - Dress outfit from older KoF's (O.O). I really like their current outfits personally, but it'd be nice to see them.
Vice - Same as Mature. Maybe give hers a tattered/Rip bottom, since she's the more brutish of the two.
Ikari Warriors Team
Ralf Jones - He's got CAMO PANTS! Increase color selection, give him a few Metal Slug Colors.
Clark Still - Remove hat, alt winposes has glasses adjustment. Or give him an alt "hat" such as a military troop helmet.
Leona Heidern - I like Rex's Mary color idea. I'd be happy if they gave her the old outfit back, for nostalgia. Or just shorts rather than full pants for alt. Give her a "Resist tapping into Blood Riot!" glare when knocked out by Special Chip KOs. Add full Orochi HOWL victory pose when win by Neomax.
Psycho Soldier Team
Athena Asamiya - A traditional outfit design, A pure Goddess Athena design (O.O!), or for Irony's sake, Give her back the Biker Shorts, and make her skirt suddenly become less obedient. A cool Chip KO could have her shifting through a few looks as she falls, until she settles on a slightly tattered one.
Sie Kensou - Give him his old "Regular nobody" outfit back as an alt. Can be based on any version of it. Loose a Nikuman Dumpling upon special KO. Chip KO has him fall on a Red Bean Paste dumpling, lookin' like Bloody murder as he lies defeated! (haha).
Chin Gentsai - Give him his 2K2 outfit, along with a color that resembles Tung Fu Rue. Or give him a Fisherman's hat, and a color that calls back to the old man from Last Blade.
K' Team
K' - More colors that seperate Top from Bottom. Iori and Kyo Palettes to go with this. and a Nameless referncing color, just for fun. Lose glasses upon Special KO.
Maxima - More Top/Bottom division colors. A few of those w/o his undershirt, like the current black/red design. Have his bionic parts explode / become damaged upon special KO. Give him more colors that reference Giant Robots (So a Gundam Color is mandatory. And like Windows K', I'd take a Voltron / Go Lion Maxima!)
Kula Diamond -Have Foxy and Diana return to assisting her back throw. Top / Bottom variety improves like DarK suggest, dunno if she needs to bare skin, lol. Maybe Make Foxy / Diana appear to catch her / Check on her for special/chip KOs.
Global Changes:
Make the victory quote pictures take on special colors! Highly unlikely, but if it can be done dynamically, this would be fantastic.
Get the artist to drawn special "Winner" pictures for special Matchups, and Neomax victories. They already did some of this for 2K2UM...
If no Color Editor is added, add up to 10 more colors per character. Either through the Alts, or just to their defaults. Give us back some of the colors we lost since the loketest, and maybe give every character on a team some kinda fun "Team Theme" color.