I think my UNO and the other newer Arduinos spend some amount of time at power on looking to see if there is a new program to be installed via USB/FTDI,
Yes the bootloader takes quite a long time, if you dispense with that the chip will start executing code within ~60mS.
Obviously using an interrupt from sleep mode has none of these issues but does draw (very small amounts of) power all the time.
Rob