Am I understanding this right that you had the correct password but no 2FA authentication and somehow a Firefox user agent on Linux triggered google mail servers to shut you out?
I never really tried with chromium perhaps I can still retrieve old data (Google Support was obviously non existing on this issue).
Also I travel a fair share (used to) and never faced any issues with any other services except gmail.
It's too stringent to assume the same machine/storage/ip are always used.
Firefox didn't work, because person deleted session and didn't have second factor (nor backup auth methods). Chromium worked, because it still had device session.
I'm traveling and using TOR and VPNs just like everybody else and haven't faced any issues. There most definitely is a problem with communicating security/accessibility tradeoffs to the public though, so I'm not putting blame on the op here.