Heard from a Googler that the internal infrastructure (Borg) is simply not optimized for quick startup. Launching a new Borg job often takes multiple minutes before the job runs. Not surprising at all.
My personal opinion is that Google's resources are more tightly optimized than AWS and they may try to find the 99% best allocation versus the 95% best allocation on AWS.. and this leads to more rejected requests. Open to being wrong on this.
I spend a significant fraction of my 11+ years there clicking Reload on my job's borg page. I was able to (re-)start ~100K jobs globally in about 15 minutes.
The origin for the info that jobs take "minutes" likely involves jobs that were pending available resources. This is a valid state in Borg, but GCE has additional admission control mechanisms aimed at avoiding extended residency in pending.
As dekhn notes, there are many factors that contribute to VM startup time. GPUs are their own variety of special (and, yes, sometimes slow), with factors that mostly don't apply to more pedestrian VM shapes.