what happens on Arduino power-on, and how long does it all take? 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.
This is something that is far far easier to measure than to try and calculate.
Here's an Arduino Uno R2 with a simple sketch that just turns on D2.  Green is the power (7V to the barrel jack) and yellow is D2.

As you can see it takes 1.544 seconds (according to the resolution of my oscilloscope which, over those time scales, isn't that great) before D2 is driven high.
The sketch is simply:
void setup() {
  pinMode(2, OUTPUT);
  digitalWrite(2, HIGH);
}

void loop() {
}