In my opinion:

KOF96 best overall game -> first of the "modern" style KOFs
KOF97 best storyline -> I love Orochi team and the tv show presentation
KOF98 best gameplay -> vsmode is gold

None of them (KOF) are bad, maybe 2k3

Why do not build a KOF collection or begin in order by KOF94 at a moderate price? (about 40$)