Although not much of a challenge now considering the level of "wtf-was-that?!-attacks" performed by the bosses that followed, but I still remember Geonitz on max difficulty being a gigantic leap above anything that Rugal could pull off in kof 94 and 95.
Runner up: Rugal in kof 94 felt like his ai was pulled directly out of Art of Fighting 2.
All the bosses that followed, including Igniz, had crazy attacks but also had ai that could be exploited in some way to achieve victory. Rugal in 94 reminded me of the input reading ai tactics employed by early fighters.
I would say Rugal in '94 is one of the hardest (especially on MVS 4 or harder difficulty settings). He can react to any attack you try to do him (he had cheap special moves, but he wasn't cheap in the same way later bosses were, where they had one or two super-powerful moves that they just used all the time). For example, if jump in on him, you will always lose, as he will hit you with his genocide cutter. If you get in close, he will grab you. If you throw fireballs, he will just reflect them with the dark barrier move. All you can really do to win is try to block his attacks, and attack him on the way down. Or try to sweep him from a distance. Usually I find I have to keep playing matches against him, until I get enough lucky breaks in one match. And I try not to lose energy (for any of the three characters I'm playing as), in the first round, where you fight the weak version of Rugal.
Goenitz is tougher than Rugal, but there are tricks to beat him.