Mark Russinovich (do fama do Sysinternals ) tinha um bom talk na recente conferência Microsoft PDC na qual ele explica o que está acontecendo sob o domínio do Windows Azure. Se você não quiser assistir o vídeo inteiro ou folhear os slides - Na verdade, muitas coisas acontecem além de simplesmente inicializar uma VM quando você solicita uma nova instância.
É claro que o acima é específico para inicializar uma VM do Windows na nuvem do Azure. Eu não tenho experiência com a oferta da Amazon, mas presumo que eles também estão fazendo um monte de operações relacionadas à infraestrutura antes de iniciar uma nova instância. Não há como argumentar que geralmente uma máquina inicializa mais rapidamente com o Linux do que com o Windows, mas eu atribui a considerável diferença de tempo de inicialização na nuvem a operações específicas de infraestrutura.