Most cloud providers can spin up an instance to SSH-able pretty quickly (seconds), if it's holding you back, you may want to look at the image you're using to boot those instances - perhaps it has dependencies you weren't hitting in your datacenter that you might in the cloud (multicast, firewall rule differences, etc). Alternatively - are you building "weird" instances? (A lot of extra disks/NIC's/resources) Those can take a longer time just to find a spot where there's locality with all of your parts (but these days that's less common).

Otherwise, if it's bare metal, I'm usually still waiting for the ram to finish counting by the time I'm done with whatever cursed thing put me back in a cage.