I think key is that both generals have already agreed on a predetermined "meaning" of each coin flip outcome, rather than having to communicate it on a different, slower medium after the coin has been flipped.

So really it just front-loads that portion (I.e. removes it from consideration as part of the proposed solution) instead of allowing it to slow down solving the overall problem. It requires precomputation/agreement beforehand, rather than during the time allotted to the problem.

The speed of that precomputation would still be unchanged, and still be the slowest portion.