I've been battling this issue for a while now and I think I've figured out what the cause is for me. Hopefully this will help others, as Microsoft's info on the matter is rather lacking.
Over the last year or so, MS have changed a couple of things relating to authentication which will have different effects depending on what type of Microsoft/Office 365 subscription you have.
The main things that effect this are whether your subscription includes Entra ID, whether this is the free or full tier of Entra ID and whether you have "Security Defaults" enabled in Entra ID. It appears that "Security Defaults" is now enabled by default.
In my case, I have a Microsoft 365 Standard subscription and this only includes Entra ID free tier. I also had "Security Defaults" enabled. With this combination, it appears that ALL standard users are FORCED to use the Authenticator app, regardless of any settings you pick. However, global admins have access to SMS and email OTP style MFA. This isn't made clear at all and in my case (as a global admin) made the issue difficult to diagnose.
With a Microsoft 365 Professional subscription (and other higher tier products) you get the full version of Entra ID (or at least a version with more features than the free one). With this and "Security Defaults" enabled, you can choose what MFA options to offer to users and they can pick which they want to use. So you can avoid users being forced to use Authenticator. But you can still force this if you wish.
With Entra ID free tier, it appears the only way to regain control of MFA is to DISABLE "Security Defaults", which MS don't recommend. After that, you can control MFA using the old "per-user MFA" settings. However, this isn't very user friendly, especially if you have a lot of users. But at least the option is there. I believe these options override the newer MFA settings configured in Entra ID. The other annoying thig about this is that the "per-user MFA" settings appear to be a deprecated feature that's being replaced by the newer Entra ID features. I'm not sure how that will affect Entra ID free tier users moving forward.
If using the "per-user MFA" settings isn't appropriate for you, then it appears the only option is to leave MFA totally disabled, which isn't ideal.
So MS have made Entra ID free tier purposely annoying and restrictive by limiting the MFA options. This forces customers to either waste lots of time manually changing the "per-user MFA" settings, decrease security by leaving MFA disabled, or spend more money by upgrading to a subscription with the full version of Entra ID.
Here's some useful links:
Feature comparison of different subscription levels, with useful info of Entra ID free tier at the bottom:
https://learn.microsoft.com/en-us/azure/active-directory/authentication/concept-mfa-licensing?toc=%2Fazure%2Factive-directory%2Ffundamentals%2Ftoc.json
Disabling/Enabling "Security Defaults:
https://learn.microsoft.com/en-us/azure/active-directory/fundamentals/security-defaults
Using "per-user MFA settings":
https://learn.microsoft.com/en-us/azure/active-directory/authentication/howto-mfa-userstates
I hope this helps other people struggling with this. If I've got any of this wrong, please comment.