Long boot delay when connecting to Arduino Mega with USB serial port

I put the Blink sample code on my Arduino Mega 2560 as a sanity check to see if the problem exists within my bad code, or the Arduino itself.
So, when I load Blink.ino onto the Arduino, it starts blinking pin 13 instantly. This is what I expect. However, when I start up the serial monitor in the Arduino software it does the reset, but then it takes about 10 seconds to start blinking again. This is happening on multiple Arduino Megas, but I have had almost instant response times in the past. I know the bootloader takes a bit of time to check if there is incoming programming data, but that shouldn't last 10 seconds.

Anyone have an idea what I am missing? Thanks.

Edit: I have tried googleing the problem, but I could only come up with stuff on the Arduino Due and stuff where the bootloader can sometimes eat some incoming data if data is sent too soon after reset.
Edit 2: If I trigger the manual reset after I start the serial monitor the sketch will start-up right away without a delay.

It's more likely your computer, not the Mega, that's causing the problem. It sounds as if you're getting the monitor window opening but the initialization of the comms is being delayed. Your second edit would appear to confirm this. Have you tried with a different USB port or a different computer?