Google employs the smartest minds on the planet and also have full insight on how Google works and what tools they have, so it shouldn't be hard for them to come up with a viable solution I believe.
Credential stuffing is a big problem. It is a really big problem for email accounts, which often are all you need to reset a password for other critical accounts. 2FA, even SMS-based 2FA observably reduces the rate of account theft. 2FA also fundamentally requires access to some extra thing that you posses, often a computing device. So it also adds friction and can lock people out (as can losing passwords). I think in part because 2FA appeared later, we seem to be okay with people getting locked out of accounts if they lose their password but not okay with people getting locked out of accounts because they cannot access their second factor.
Library computers are also untrusted devices. They are also not the only untrusted devices that people want to use to login to their accounts.
As for solutions.
Printable access codes are supported in gmail. This is a pain to do over and over but does permit 2FA without any additional computing device. You can let people disable 2FA (which is possible), though you can expect another letter pointing at the suffering this causes and arguing the opposite.
You could enroll the library in a "Bob uses this library to authenticate, don't ask for 2FA here" mechanism that does not use cookies but I'm not sure what this would actually be given that the library is deliberately resetting state on the machine after each session. Perhaps there is some acceptable state that the library could keep around? A solution in this vein requires coordination between email providers and libraries but is maybe the most promising approach. Or you could do something like a family account that permits the librarian's account to tell gmail to temporarily permit 2FA-less logins for a particular account/device pair.
You could recognize that 2FA most protects against stuffing and not let people choose their own passwords to guarantee uniqueness, but I suspect you'll get an equal number of people who fail to remember their long password of random characters and get locked out, leading to a similar letter complaining that Google is harming people who need memorable passwords.
I'll print out all the comments and forward them on to the Free Library. The next time a patron gets stuck, the librarian can read one of our comments out to them.