On some (most?) CentOS images, the default /etc/sudoers file enables requiretty to sudo. We disable this on Google, but need to do the same on other providers, as we cannot be sure that this setting won't be enabled on some images, especially non-default images.
The solution is to either disable requiretty everywhere, or change ssh_exec! to always request a TTY.