After integrating Firebase Database, my alpha builds started failing with an unhelpful "Developer Error".

I found this post explaining you should whitelist the SHA1 of both the debug and release version in the Firebase Console. Indeed, I had forgotten to add the one for the release version.
So I ran the command to get the SHA1:

keytool -exportcert -list -v -alias TheAlias -keystore path_to_keystore

I added it to the whitelist in Firebase Console, then tried again. Same error!! Then I remembered that the new publishing mechanism for the Play Store is that when I upload my signed APK, they remove my "upload signature" and sign the APK with their own "publishing signature".
It turns out, the SHA-1 of the App signing certificate is readily available on the Google Play Console under Release Management, App Signing. I whitelisted the SHA-1 and this time it worked.

Feb 2023 update

You will now find the SHA-1 in the Google Play Console under Setup, App Integrity, App Signing.