It's getting more and more mysterious!
Trying Serial.begin rates from 9600 to 115200, only at 57600 is Ok.
Yellow (L) Led blinks twice and messages appear immediately !
All other rates do what i described above!
So, the problem might be the timing during software reset.
This has had me scratching my head for a while. It does seem to be a problem specific to the latest bootloader on the mega2560, and the way it interacts with the IDE (1.0.2 at least - I haven't tested with other versions). I can confirm your observation that execution being passed to the main program is delayed several seconds (~5 or 6 seconds in my case) _except_ when the baud rate of the Serial monitor in the IDE is set to 57200.
No delay problem on Mega1280, Uno, Leo etc.
Two other things:
1) If you open the Serial monitor on the IDE at 57600, even if the Serial.begin on the board is set to a different baud rate (e.g., 115200), you still don't get the delay. (You get gibberish on the screen, of course, but you can see the sketch starts to execute without the delay).
2) If you open a Serial monitor _outside_ the IDE (e.g., using Putty), you don't get the delay, even if you open it at 115200. Works normally without a start-up delay for Putty at all baud rates I've tested.
So the problem seems to be an interaction specific to the IDE and the Mega2560 bootloader when the IDE opens a Serial monitor at any baud rate I've tested, except for 57600. Clearly nothing to do with USB hardware and bootloader interaction at all,
Which is good to know, because until I came across this thread I thought the new Mega2560 bootloader had a 5 second delay built-in on reset. Now that I know it is just an artifact of interacting with the IDE, it sounds like a much less serious problem.
Good find on the 57600 "special case"!