By "the size" I meant to say "the size of the infrastructure", meaning that AWS has to manage orders of magnitude more instances than Hetzner. This might as well contribute to "things" being slower.
I guess I'm just struggling to see how having more VMs means it takes longer to provision one? A database query to find the space and get an allocation should be milliseconds in either case.