Regardless of which 2FA app you are using, you should still be writing down the back up codes given by each site on to paper and storing them securely, much like a mnemonic phrase.

You are correct. Even sites which specify "Download the Google Authenticator app" (which unfortunately many sites do), will still work just fine with a different 2FA app.