Google Authenticator doesn't support the export/import function, so you need to have access to the application if you are about to switch devices whereas Authy is one of the popular 2FA app that works on multiple devices when you login to your account.
Google Authenticator can be exported to another Android device without any issue. I have done it in the past so anyone can be using an Android handset. Clicking on the three dots on the Authenticator screen and following the screens, is a very easy process.
I am using Google Authenticator, and that's why I said it is hard to recover the accounts if they are gone one time, like if the device is lost, the OS of the phone got corrupted, etc. Any type of reason could cause a loss of access to this app. It is just too risky. I get to know about other 2FA apps too, but I think Google is more trustworthy, or isn't it?
You can create a backup of your Google account on your Google Drive to retrieve all Google accounts. Ensure that the email address you have used to log in to your Authenticator is not lost or stolen, I meant the password. There are tutorials on how to create a backup if you search on Google, the next step will be to log in to the new Android device using the same email address and password to get access to your authenticator.
The new Android version or the version earlier allows users to create separate passwords to access any app. I think if your phone gets stolen and somehow the thief can unlock the password, the struggle would be to unlock important apps on your phone with this feature to lock apps. Android is not so bad as you both have projected it with your comments.
As Theymos said it is important to get your email address secure as without it situation would be bad for anyone using an Android device.