Did some timing runs to compare with your observations.
From "power on" with NO SD Card to:
Red/Green combination flash - ~9 seconds
Green only flash - 16 seconds.
Picture on-screen - 32 seconds. (Immediately replaced with "no SD card" message)
From "power on" with freshly formatted (empty) 2GB SD Card to:
Green flash - 16 seconds.
Picture on-screen - 32 seconds.
(same as no SD card, but LED sequence slightly different during startup)
From "power on" with freshly formatted (empty) 16 GB SD Card to:
Green flash - 16 seconds.
Picture on-screen - 32 seconds.
(same as 2GB SD Card)
From "power on" with about 12 Gb of data on the same 16 GB SD Card to:
Green flash - 16 seconds.
Picture on-screen - 42 seconds.
The only thing I see from this experiment is the possible suggestion that more existing data on the SD card takes more time to fully initialize the camera. Not likely to be the only thing that can affect start up time, of course.