My experience with changing devices or cities (or god forbid both at once) is that it always requires further authentication, and often fails outright. I have an account which is simply disabled because I didn't set a recovery phone # or email and then changed machines. Everyone I've ever discussed the topic with has described similarly pervasive problems.
Which makes me wonder: what's so different between usage patterns? Obvious Google's auth approach is working for lots of people, so what's distinctive about this block of users who it's constantly failing for?
That's exactly it, there's already two Gmail accounts from high school I can't access despite knowing the passwords.
Google™ employees have come in and found mind-bending ways to excuse it when I've mentioned this before.
But just as you said, they are giving it away for free, so it is technically theirs, we are not paying customers. (Except for G-Suite users)
In my experience (it is already the case with gmail and outlook up and now), this means I will not be able to login to my account when in holiday in another city, country, or when I use a borrowed device, or when I am behind VPN/Tor, etc, unless I give google my phone number, and can afford to get a call / sms at that point of time and unblock the account.
It should be my choice, as it is my account that is at risk, to turn on/off such dubious security measures. It is fine to have these features on by default, but I would like to turn this particular feature off for my account. Any clever "risk assessment" thing where a computer decides without an option to turn if off/on is problematic.
I have sometimes the feeling they know this and it is on purpose. They want not only to collect data, they want to collect high quality data and these measures help to clean their data sets at time of collection.