Hello Jonathan,
Have you had a look at your logs? In Cloud Console, you should navigate to logging and examine logs for any relevant message. To narrow down your investigation, you should select logging level as "error", or "debug". As a first step, if you notice session support is not enabled in appengine-web.xml, try editing appengine-web.xml, and adding line: <sessions-enabled>true</sessions-enabled>.
Does situation come back to normal if you revert firebase-admin sdk to a version prior to 3.x?
You are encouraged to open a private issue with similar contents in
Public Issue Tracker, where private details, such as project names, can be exchanged safely, away from public scrutiny, if you mark the issue as private. Public forums such as Groups are not suitable in this respect.