It's a tough call really... no question, as Tak says, if you're a collector, but for the gamer...
Well, my choice would be '97, '98 and 2000.
KoF '97 has a very good roster, the best presentation in any KoF to date (imo), and a superb battle layout for one player. The game shows the end of the Orochi saga, but you can easily piece togther what went on previously. Best one player koF yet.
KoF '98 has a 1st class roster, a good battle layout for one player and is awesome for two players. So storyline as such, but Rugal appears in his best version.
KoF 2000 has a good roster and although is inferior to '97 and '98 has the best Striker system of the KoF games '99 - 2K1. It's good in one player, and good in two player, but simply worth owning because of the newer characters to play and the improved Striker system over '99.
If you're mad on the storys behind koF and how the characters are involved you really need to start at '94 and work your way through to KoF 2K2.
Personally I feel '95 and '99 are the weakest in the series in terms of gameplay.
Briefly -
'94 - still a top game, some fantastice backgrounds, but no team edit and limited special moves.
'95 - impoved graphics and sound, introduction of team edit, but flawed gameplay - the damage system is really harsh.
'96 - 1st class presentation, brill sound and one of the best boss stages ever, plus you can select the Boss Team (big bonus).
'99 - very good backgrounds and nice character additions, but Striker system is lame and ruins the game.
2K1 - doesn't know if it wants to be '98 or '99, but good fun... poor colour scheme, and reduced animations
2K2 - decent addition, good sound, nice bgs, but again naff animation, and some characters are poorly drawn and redesigned (especially Rugal)