Just hit a relative of this a couple of days ago. Solution:
1) Turn on two-factor authentication.
2) Create an application password for your e-mail client. You use this just like a password, although it's meant to be set in a program and forgotten, it's not something you need to remember. It's actually just a secondary password for your account, 16 random alphanumeric characters.
Effectively, they took a sledgehammer to ensuring that your password can't be brute-forced and greatly reduced the exposure surface for other attacks on it. I have no idea why they require two-factor to be turned on in order to use it, perhaps this is just a carrot-and-stick to get you to turn on two-factor.
Note that the less-secure-applications switch is old information, no longer useful.
In theory this change was rolled out 6/1, but it appears to be a roll-out, not everyone got hit at once.