The only connection between download time and this problem is the ATmega16U2. It handles the download and the USB/serial communication to the serial monitor.
I tried adding some error checking to the UART driver. I rejected characters with framing or overrun errors but it didn't help my problem. I still get at least one junk character when I bring up the serial monitor.
I think I have a work around for what I need. This seems to prevent the problem of my examples executing on junk input:
void setup() {
Serial.begin(9600);
while (!Serial) {} // wait for Leonardo
Serial.println("Type any character to start");
while (Serial.read() <= 0) {}
delay(200); // Catch Due reset problem
// assume the user typed a valid character and no reset happened
}