One point of clarification before getting going: there's nothing magical about using Google Authenticator or Microsoft Authenticator or even Joe Bloggs Authenticator from some third party - they're simply ways of storing the special tokens that are given to you online for each account you register, and they all use the same time-based verification methods so that your login attempts are all limited to 30 seconds per generated code and thus making sure that criminals can't use these codes after the fact. Which is why I can share the screenshots below without worrying about my own security!
Now, in practice, I wouldn't recommend using 'Joe Bloggs Authenticator' (or similar) because you just don't know what the developer is doing with your information, even if what is kept isn't actually enough to do a full login with one of your accounts. So I'd always recommend you go with a major developer like Google or Microsoft.
Now, while Google's tool works well enough, Microsoft's equivalent just leap-frogged its rival with a huge new feature: cloud backup of your accounts and tokens. In other words, if you get a new phone and want to use Google Authenticator, you'll be frustrated by having to go into every single service all over again and request a new QR code to get a new token generated in the application - it's a right pain and takes time, especially when you have half a dozen accounts established with two-factor logins.
But Microsoft Authenticator now offers cloud-based backup of these accounts so you can replace your Android phone, install the Microsoft Authenticator app and tap on 'Begin Recovery' and, within seconds, all your accounts and tokens should be back with you, for easy two factor authentication day to day. Well, in theory. It mostly works though, as you'll see.
NB. Windows 10 Mobile has a Microsoft Authenticator UWP application and you may be getting excited at this point. However, calm down, since this application is too old to get the cloud backup/recovery features and I'm not optimistic of an update. So this tutorial is for anyone moving up from a Windows phone to an Android phone (or iPhone, in theory all this works on iOS too, though I haven't tested it).
Here's a walkthrough then. Step zero is, of course, to install the Microsoft Authenticator application from the Play Store, so let's assume that this has been done.
Now... I've been testing this on a number of Android phones and while recovery does work, not all accounts seem compatible, and thus don't show up on the new phone. I suspect that an update to Microsoft Authenticator might solve this, and it's early days.
Well worth a try anyway, it's free in the Play Store. It's all free and if, like me, you do change phones fairly often, for whatever reason, then switching from Google's to Microsoft's Authenticator should save quite a bit of time and trouble each time.