Yeah, GMail's security is terrible in that regard and having learned about their geolocation policies I basically never use them for anything now.

If you're in the Apple ecosystem, iCloud is actually pretty good. Lets you generate and manage random email addresses for different things too, so you can give to a nonprofit or a campaign and not be forever spammed for donations thereafter. Plus, their authorization system is device-based so assuming you don't lose access to all your devices, you can get in pretty easily even from webmail in a different location.