Just taking a stab here. I know that EE is very PHP version specific. I would check the php version installed and maybe even check which php versions are available on the server. I would go with v7.2 at the least and maybe v7.4 if available. i forget what is available in the 16.04 repos.
I do have a question. Why 16.04 and not 18.04 or 20.04? You will always get the latest versions of packages in the repos with newer server versions and you don’t have to wait for developers to backport their packages to older server versions. Plus 16.04 is End Of Life April 2021.
So if you can use 18.04 or 20.04 I bet your issues go away. I have been rolling out VPS with 20.04 and with the exception of a single instance of having to roll a system PHP v8 back to v7.x I have not had any issues.
Try the following to check PHP versions:
php -v
to show which version is running
sudo update-alternatives --display php
to show available packages
sudo update-alternatives --update pho
to change the default system version of PHP.
Hope something here helps!