>My Android is running Lineage without Google Play Services (no microg either).

>Firebase flat out refused to allow me to login because of Google Play Integrity

Sounds like the issue is that you don't have play services installed, rather than play integrity specifically.