Reading up on something and apparently I can set any locale as the default locale for a cloud instance, provided I choose "C" since that is the only one that works. Also, for ssh connections it by default uses any locale specified by the client, provided it specifies "C" since that's all that it has.

(Free from Blackadder's "last meal" scene, where the prisoner could choose any last meal, provided he chose sausages since sausages was the only thing the cook made)

(I see the info about dpkg-reconfigure locales to install extra locales, but that is manual and only after a cloud instance has been instantiated. I was looking into what cloud-init can do for me)