Level 2-3 now complete. Note that I intentionally did the third bomb slightly slower. That way it didn't explode and I had enough health to beat the bosses in the fastest time possible. Note that the fastest boss fights rely on manipulating their behavior so that ideally you can kick as frequently as the game allows for the whole fight without ever missing.
Level 2-2 is now complete. So far it looks quite fast, under 10 minutes. If you guys have any suggestions for additional optimization so far, feel free to post them in the forums page created by goofydylan8 in 2012.
This completes all stages up to 2-1. Notice that there are a few moments where is looks like a character switch is needed to yield faster results. Caution must be careful as each character has an advantage over the other some skill. Specifically, Martin Riggs (Mel Gibson) can jump higher and reach more places from the ground, while Roger Murtaugh (Danny Glover) can pick up and toss boxes that will kill enemies instantly. Level 2-1 was the hardest level to run so far since I had find when the character switches are worth it.