"We are now using Entra Free, and do not seem to have access to the Conditional Access settings that are required to perform this required action of enabling MFA for our users. It seems we would have to upgrade to at least Entra P1 to get access to this. Is that correct? "
Not necessarily, upgrading gives you granular control. But regardless of your plan MFA is going to be required going forward after the setdate.
If MFA is not applied by the set date, MFA will be automatically enforced. Since you do not have Conditional Access you could leverage Security defaults as well. If you don’t want to use Security Defaults, you will still be able to have MFA enforced automatically after the deadline, but Security Defaults allow you to proactively meet the requirement.
You could also choose to postpone enforcement.
For detailed planning I will recommend you take a look at: https://learn.microsoft.com/en-us/entra/identity/authentication/concept-mandatory-multifactor-authentication?source=recommendations
You can mark it 'Accept Answer' and 'Upvote' if this helped you
Regards,
Abiola