FWIW, I stopped using Linode a long time ago because their OS images are utterly terrible compared to mainline distributions found on DigitalOcean, Azure, AWS etc. A lot of components are oddly missing. The only good thing about Linode is Lassie
Might be worth trying your same steps on another provider such as DigitalOcean or Lightsail. If you get through, it’s definitely Linode’s issue and you would have narrowed it down without much effort.
If your steps don’t work on another provider, then you can look into the EE configuration logs more deeply, since EE4 otherwise fully supports Ubuntu 18.04 LTS.