Turns out, it was a false fix. The problem was still there but I think we've found the root cause. It seems to happens when users connect directly to app.powerbi.com without first connecting to Office365. Our Office365 tenant (Azure) is forcing MFA but since the user did NOT connect to Azure first, when we try to share a dashboard, PowerBI tries to talk to Azure and that fails because MFA wasn't done. Inspecting the browser network communication, we see that Azure returns a 'AdalMultiFactorAuthRequiredErrorCode'. If we log into Azure (and MFA) first and THEN, connect to PowerBI, then sharing works.
Microsoft wants to close the case since we were able to share the dashboard but the underlying problem is still there, which is PowerBI do not use MFA. In my mind, this is a major problem because of the data that could be shared through PowerBI if the account password is compromised. It is my strong recommendation that Microsoft fixes this.
Is this a known limitation or something particuliar with our Azure/PowerBI environment? Meaning, if YOU have MFA mandatory in Azure and YOU connect to PowerBI without first connecting to Azure (and have disconnected first from Azure and cleared your cookies), can you share a Dashboard with other users? It's 100% reproduceable here.