In any non scrolling/slow scrolling area (trains, bosses, etc.) the fastest method of movement is crouching followed by walking on alternating frames.
I remade the second boss fight, but there seems to be some set frame rule as to how fast I can complete this fight. I'm not sure if it's his vulnerability or his jump. I'm getting tired of the fight so I'll redo it if I make a publishable run, which I intend to do at this point.
This also shows off my new movement tactic at the end. ^_^
http://dehacked.2y.net/microstorage.php/info/926274445/Bad%20Dudes%20Stage%202%20New%20Kirkq.fcm
I'm currently at the third boss (not updating the WIP for a while). I will be able to kill him in three phases as opposed to 4 hitting him with dagger-dagger-flaming punch.
Another thing I found on GameFAQs: A charged punch charges while the game is paused, so I can pause with the boss in a better position while still charging my punch.