1. A computer-implemented method for providing an instance availability estimate in a distributed execution environment, the method comprising performing computer-implemented operations for: collecting data defining actual boot times for one or more virtual machine instances, the one or more virtual machine instances having a plurality of combinations of instance types and operating systems; utilizing the collected data to compute an estimate of a time required to boot a virtual machine instance having each combination of instance type and operating system; storing the computed estimates in a historical boot times data store; receiving a request to launch a new virtual machine instance; in response to receiving the request to launch the new virtual machine instance, identifying an instance type and operating system for the new virtual machine instance; utilizing the instance type and operating system identified for the new virtual machine instance to retrieve an estimate of the time required to boot the new virtual machine instance from the historical boot times data store; utilizing the estimate of the time required to boot the new virtual machine instance to compute an instance availability estimate for the new virtual machine instance; and providing the instance availability estimate in response to the request to launch the new virtual machine instance.