Dr. Cranor's advice is super sound, and that's the first step. But, what's not mentioned, and it's super, super important to know, is that customer service reps can still be tricked into letting anyone into your account with just the last 4 digits of your SSN-- you just have to be nice enough and sound confused. So, be sure to call your carrier and have them place a "security note" on your account saying something to the effect of "Only proceed after giving complete security PIN/password".
This one was especially painful, because even accounts that offer hardware and/or software token-based 2fa still can be downgraded to SMS. Especially Google. So, while it's imperative to use the authenticator app, and get yourself a Yubikey, SMS is still going to be a factor to deal with. You need a phone number that no one knows about. Get a jack phone from another carrier, with a cheapo text-and-voice only prepaid plan, and link it as your backup phone (and secure that account with the carrier, too!)
You can also use Google Voice (and similar) accounts in certain instances, but there are caveats and questions. Some services honor numbers that don't come from establish carriers, and others do not. (So, Google will honor a Google Voice number as your backup, but you can't sign up for, say, a Twitter account with a Twilio number.) Also, there is a certain amount of linkability between users and their phone numbers (cough cough, Facebook) which might prevent you from keeping your phone number secret. I'd like more research here-- what are your thoughts, everyone?
As you can expect, the attacker logged into his accounts over PIA. We should really lobby Google to allow users to choose whether they'd like logging in over VPN or not. (This could be toggleable, and maybe have a whitelist option, so you can use your, say, work VPN as an exception...)