Edit: when I say anything, I'm not talking user programs. I mean as in, before even the first instruction of the firmware -- before even the virtual disk file is zeroed out, in cases where it needs to be. You literally can't pause the VM during this interval because the window hasn't even popped up yet, and even when it has, you still can't for a while because it literally hasn't started running anything. So the kernel and even firmware initialization slowness are entirely irrelevant to my question.
Why is that?
You also need to start OS services, configure filesystems, prepare caches, configure networking, and so on. If you're not booting UKIs or similar tools, you'll also be loading a bootloader, then loading an initramfs into memory, then loading the main OS and starting the services you actually need, with eachsstep requiring certain daemons and hardware probes to work correctly.
There are tools to fix this problem. Amazon's Firecracker can start a Linux VM in a time similar to that of a container (milliseconds) by basically storing the initialized state of the VM and loading that into memory instead of actually performing a real boot. https://firecracker-microvm.github.io/
On Windows, I think it depends on the hypervisor you use. Hyper V has a pretty slow UEFI environment, its hard disk access always seems rather slow to me, and most Linux distro don't seem to package dedicated minimal kernels for it.