Running the Exchange Hybrid Configuration Wizard showed an issue with connecting to Exchange Online:
Connecting to remote server failed with the following error message: Connecting to remote server outlook.office365.com failed with the following error message: The WinRM client cannot process the request. Basic authentication is currently disabled in the client configuration.

Open Command Prompt and run the following to validate if Basic auth is enabled:
winrm get winrm/config/client/auth

Running the following will enable Basic auth:
winrm set winrm/config/client/auth @{Basic="true"}

Then going back to the Hybrid Config Wizard shows Succeeded for both On-Prem and Online:

I also had a similar issue with connecting to Exchange Online PowerShell that gave me the following error:
New-ExoPSSession : Create Powershell Session is failed using Oauth

Basic Auth is disabled and can be seen when running this command:
winrm get winrm/config/client/auth

Changing Basic to true in Powershell is slightly different vs Command Prompt and requires the single quote marks:
winrm set winrm/config/client/auth '@{Basic="true"}'

Connecting to Exchange Online now is successful:
