Tough call. It would have to be a tie between Goenitz and Orochi. Goenitz clearly had the least amount of screen time out of all of the KOF bosses. Futhermore, they didn't dwell that much on his past (sure, most of us know that he took out Rugal's right eye, and that he killed Chizuru's older sister, but what did he do before that? Was he a stock broker who became irate after seeing Maximum Overdrive in a nearby movie theater? Who knows?).
Orochi, on the other hand, was the icing on the cake. Once he made his grand appearance as the final boss of KOF 97, I became greatly worried. After he slaughtered my team in about 60 seconds flat, I thought to myself, "This is the big, bad Orochi? No wonder so many people feared him." It would've been fun to play as him in KOF 98, but I guess that never happened.
As for my least favorite KOF character that SHOULD'VE appeared only once, that would be a tie between Li Xiangfei and Hinako (USELESS! ANNOYING! Both of them!).