So I have used Authy, which apparently is somehow protocol compatible with Google Authenticator, and you can back up your tokens with a password. I got a new phone, installed the app, entered the password, and all my tokens were there.
Nothing mysterious. Authy and Google Authenticator simply implement the same standard, RFC 6238.
SMS 2FA is a different proposition, in that the authentication provider sends you the intended response directly. This is a little easier for nontechnical users in that it doesn't require an app that can compute TOTP responses, but it's markedly less secure in that anyone receiving or intercepting the SMS can immediately respond to the challenge, and less resilient in that you can't authenticate at all if you don't receive the SMS - which is the failure mode under discussion here.
Maybe they've fixed that since then, but I don't care. I'd rather risk a theoretical flaw in Authy's E2EE than risk getting screwed again, and by now much more thoroughly, by the flaw I know about in Google Authenticator.