I'm having the same problem, but have done a bit more debugging.
At first I used my users credentials and everything was fine.
Then I switched to Client ID and Client Secret, and the error was:
401 Client Error: Unauthorized for url: https://[tenant].sharepoint.com/_api/Web
This command resolved that issue
Set-SPOTenant -DisableCustomAppAuthentication $false
After this everything was fine.
Then I switched to certificate, and the error is:
('-2147024891, System.UnauthorizedAccessException', 'Access denied. You do not have permission to perform this action or access this resource.', '403 Client Error: Forbidden for url: https://[tenant].sharepoint.com/sites/MySite/_api/Web')
But the wierd thing is that the error only comes when accessing a spesific site like:
https://[tenant].sharepoint.com/sites/MySite
If I change the URL to the root (or whatever its called), I have access:
https://[tenant].sharepoint.com/
But that does not help much when I can't access the sites.
Relevant information from Get-SPOTenant:
LegacyAuthProtocolsEnabled : True
DisableCustomAppAuthentication : False