Here's what I think happens and how long it takes (FIXME means I don't know). I'd like to end up with solid max times for everything if possible.
Power-on, input caps to the 328P begin charging and Vcc to the 328P rising
From the time it first comes to life, internal 328P hardware holds an internal reset line low.
Vcc to 328P climbs past the power-on reset voltage threshold V_pot, which has a maximum value of 1.6V (see the ATmega328P_datasheet_revision_DS40002061A.pdf Table 29-11). For a 9V battery with a typical internal resistance of 2 ohms, the time constant with the ~100 uF of input capacitance on the Arduino is RC = (2 * 0.0001) = 0.0002 s. So this normally happens pretty fast, but note that if additional loads are connected to the Arduino Vcc or Vin things might take longer.
A reset timer on 328P begins running. When it expires the internal reset line will be released. How long this timer will run depends on fuse settings. For the default Arduino fuse settings the timer will run for about 65 ms. For a 3.3V Arduino variant the typical time will be slightly longer (~69 ms). See ATmega328P_datasheet_revision_DS40002061A.pdf Table 29-11 Chapter 9 for details.
The PD7 line of the ATMEGA16U2 chip on on the Arduino holds the external reset line low past the point in time at which the internal reset is released, which causes the EXTRF bit of the MCUSR register on 328P the 328P to end up set (indicating an external reset). FIXME: does it actually work like this (hold it low longer)? FIXME: How long exactly?
The external reset is released by the ATMEGA16U2
The bootloader on the 328P begins executing
The bootloader examines the MCUSR and finds that EXTRF is set, but WDRF of MCUSR is not set. It therefore quickly flashes the on-board LED several times and the attempts to download a new program over the serial line. This process takes about 1.6 s total.
The download attempt terminates with a watchdog timer timeout and consequent watchdog timer reset. The EXTRF bit of MCUSR remains set (it is sticky and is only cleared by a power-on reset or explicit 0 write). Time: pretty quick
The bootloader starts executing (again). Time: pretty quick
The bootloader examines the MCUSR and finds that the EXTRF and WDRF bits of the MCUSR are both set. It interprets this to mean that the bootloader just executed and terminated due to a watchdog timeout, i.e. it decides that an upload attempt has already been made. It therefore clears the WDRF flag (since it thinks it probably set it itself) and jumps to the start of the application flash instead of making an upload attempt. Time: pretty quick
All the setup code required to provide the C environment your main() program requires runs. This includes for example copying global variable intial values from flash to RAM, etc. Time: FIXME?
main() begins executing.