Your list is lacking the cheapest bosses.
Igniz -- KOF2k1
He's got some crazy cancels (and infinites... which I'm grateful the AI doesn't use), insane priority on the majority of his moves and a Super Bar that's always full.
Not to mention he loves to bust out those uber-damaging DM's like they're going out-of-style.
Shame that he can be easily beat by Bao, with a simple spamfest of QCB + K's.
and
Johann -- ROTD
He's actually a piece of cake once you learn his attack pattern, but before you learn what it is, man... what a pain.
But neither of them matches the pure cheese that is '95 Rugal.
He gets my vote.