There are many schools of thought here, and people will mostly disagree with me. But!
'96 is the first “good” KoF, the one where everything coalesces into the feel we now know. It’s also one of the most visually gorgeous games, and the game where we first hear some of the most recognizable musical themes. And yet, it’s one of the rarest in the series. One almost never sees it re-released. So this seems like an opportunity.
The three NESTS games ('99-2001) are peak KoF. Most people only really like 2000, and that sort of reluctantly, but phooey on that. '99 is the single prettiest game in the series, has the very best music, the most coherent aesthetic and storytelling, one of the best casts, and is probably the most creatively bold SNK has ever been, trying to reinvent their flagship series on every level.
2000 is the same game again, with balance tweaks, more content, and slightly blander stages and music (though still some of the best music ever). It has the best intro and some of the best endings in the series. It’s one of the last games SNK made before bankruptcy, and they knew they were dying, and that feeds into some of the creative decisions here.
2001 is my very favorite, and one of the “worst.” It’s a work of chaos. SNK is dead. Random minor parties pounced on their corpse for parts before they could regroup as Playmore, and somehow rehired most of the former SNK to make a new game on a reduced budget and timescale, according to new creative demands. The result is pure decay. The NESTS saga wraps up in the most expressive game in the series, with weird art, weird structure, weird music, weird new characters, weird storytelling that’s all just blood, rusted chrome, and tarnish. There is no balance, the whole thing is baffling, and it is amazing. Everyone hates it. It’s the best one by a wide margin.
2003 is another rare one, the first proper Playmore-era game, that tries to pull another '99 out of the hat with less money, lacking much of the old creative staff, and with anxiety over putting off the twelve people who still cared at this point, most of them in Mexico. It’s interesting, and worth a look-in. If XI were available, that is the 2000 to 2003’s '99, except in this case it’s actually the bolder, better, and much, much rarer game, with maybe the third-best soundtrack and probably the best roster and game system ever. It’s a superb game, and I wish it had more exposure.
Don’t bother with vanilla '98 when it’s the most widely available game, in more elaborate forms that also include the original. Vanilla 2002 is terrified, reactionary rat barf, catering to bad Gamer impulses and resulting in the most artless, conservative game in the series. 2002 UM is… fine, though. SNKP salvaged it as much as they reasonably could while still pretending it was the same game. It’s not interesting, but there is a lot of CoNtEnT and they put genuine effort in.
'95 isn’t super interesting and plays strangely by post-'96 standards, but it’s a notable relic. It is literally the same game as '94, except with one team replaced (and Iori introduced), plus different levels and music and the ability to build your own teams. '97 is the same game as '96, but less pretty, with less memorable music, more widely available, and the most important plot function/true ending in the series.
SO THOSE ARE MY THOUGHTS.