Based on the info you shared there are currently the following reasons possible:
1.) Make sure that AutoDiscovery is working and that the SCP is configured correctly (see here as starting point). If that isn´t the case you could try to use a local overwrite from that (see here as starting point), but I would prefer to fix autodiscovery. If you have Outlook 2010 (must be fully patched to connect to Exchange 2016 due to mapi over http) you could check the following howto.
There is an difference how autodiscovery works for Domain joined PCs and non Domain joined PCs. As a starting point check the following website.
We might find issues in the Microsoft Remote Connection Analyzer (but that depends on your setup & environment).
2.) If you use an internal PKI for the SSL certificates on your Exchange server the root certificates should be automatically pushed to every domain joined PC.
However if the PC isn´t domain joined then the ssl certificate used on Exchange aren´t trusted due to the reason that the root isn´t trusted. Depending on the OS configuration you should get a trust error message to bypass but we do not know the configuration here to say that for sure.
3.) If the client can be configured but has connection issues, post us the connection info's (see here for a howto) [remove sensitive infos here if needed]. If it stopped during a configuration step, then it would be usefull to get an screenshot from that.
4.) Make sure that Outlook and Exchange are fully patched.