Enabling Modern Authentication on 365 Tenant

Enabling Modern Authentication for your Office 365 tenant gives that tenant the ability to issue and validate authentication and refresh tokens (OAuth2.0 tokens) for thick clients like Outlook.
In essence, you are simply enabling another auth provider -- it is not directly tied to MFA. As long as the client supports ADAL/Modern Authentication, it will follow the new authentication process (with or without MFA), and if it does not support it, it will use the legacy method.

• Without Modern Authentication enabled: Outlook will prompt the user for username + password in a popup.
• With Modern Authentication enabled: Outlook will display a mini browser to lead the user through the authentication workflow.

It does not affect logins through a regular browser. Because of this, you could leave Modern Authentication disabled, but still federate authentication through AD FS or the Duo Access Gateway (DAG) and still see the Duo Prompt in a regular browser. Outlook thick clients would be limited to basic authentication (username + password).
Source: https://help.duo.com/s/article/4250?language=en_US

Also confirmed by Microsoft Azure Technician.
The Process

1. Enable MFA using Azure Active Directory: https://docs.microsoft.com/en-us/azure/active-directory/authentication/howto-mfa-mfasettings     It also describes how to generate App Passwords. App Passwords are required for Office 365 clients that cannot handle MFA. App Password actually bypass MFA so use them only if needed.
2. I tried to add my office 365 account in the mail client for my IPhone. To my surprise it allowed my to enter my password and MFA code to configure my mail account. It did not require using App passwords.
3. I tried to add my Office 365 account to Outlook 2016 on windows 10. It failed to add my account and did not show a helpful message.
4. To resolve above issue I had to enable modern authentication on my office 365 tenants. The steps were:
   1. Connect with Exchange Online PowerShell using the steps below: https://docs.microsoft.com/en-us/powershell/exchange/exchange-online/connect-to-exchange-online-powershell/connect-to-exchange-online-powershell?view=exchange-ps     When you run the script  you will need to use your App Password to authenticate with Office 365
   2. Once you are successfully connected you can view your current settings for OAuth2ClientProfileEnabled using the command:

 Set-OrganizationConfig -OAuth2ClientProfileEnabled $true

Get-OrganizationConfig | Format-Table -Auto Name,OAuth*

Name OAuth2ClientProfileEnabled
---- --------------------------
 xxxxxxxxxx.onmicrosoft.com True

Source: http://www.rajinders.com/2018/10/15/enable-modern-authentication-on-office-365/

Enabling Modern Authentication on OnPrem Exchange

If the tenant in question has a hybrid setup with Exchange onprem, then the same command will need to be run there.

We had trouble with Church Hill's onprem exchange that meant we could not connect through powershell, the following workaround worked:

Recycle the powershell app pools in IIS