Riiiiight. So having confirmed that it works with the terminal program, even if the same sequence of commands are sent, about the only point of difference left was the timing of the LED pulses.
I modified the Optiboot hex file to reduce the number of pulses from 3 to 1, mindful that at 16MHz they would be twice as quick, but also that the sync commands are sent while the pulses are still happening.
And now it works.
avrdude still sends three sync commands. The first one still arrives while the LED is pulsing, but in theory this time the UART FIFO doesn't overflow. Like before, the characters are pulled off as soon as the pulsing finishes, and the response is sent. The response to the next two sync commands is sent immediately, as all all the responses to the commands that follow.
So.... wha? How, in the first case, did Optiboot manage to pull a sync command out of the FIFO, but then get stuck on the next command? Why would the lack of FIFO overflow make a difference?