What worked for me was
Unchecking everything in Build Settings => Player Settings => Publishing Settings => Build
Clicking Okay in the dialog that pops up
Downgrading the Firebase Core Unity package to version 11.6.0 (as well as the Auth and Database packages in my case)
To me this appears to be a bug in the Unity Firebase Core package. Hopefully Google will fix it. I tried to downgrade to newer versions than 11.6.0 but it was the most recent one that didn't show errors