I remember there is ksplice or something like that to upgrade even the kernel without a complete downtime. Everything else can be upgraded piecemeal, provided that worker processes can be restarted without downtime.
If the hardware itself is the reason for the long startup time, kexec allows you to boot a new kernel from within an existing one and avoids the firmware/HW init.