It's even easier for Github and Google Mail. For web services, the right stack is:
* Hardware U2F token
* Backup software TOTP (Duo or Google Authenticator or whatever)
* Backup printed (or saved on offline USB key) passcodes
* Disabled SMS.
Unlike SMS, which is devastating to security even as a fallback, having a software TOTP option is basically fine; most of what U2F buys you is unphishability. This leaves you with two levels of backup, one of which is reasonably secure indefinitely.