Configuring preferences and options in Outlook.com
Shouldn't need to change password, but for me, I needed to add an authenticator for 2FA for the relevant App Password section to show up. After clicking "Security", then "Manage how I sign in", should be able to see something like this if the relevant Two-step verification settings are correct:
If your Two-step verification shows ON but "App passwords" doesn't show up I would probably suggest trying the age old "Turn it off and on again?" troubleshooting method.
I was already using Google Authenticator on my android phone for other purposes so it was simple to scan the QR code the webpage provides with Google Authenticator to add Microsoft's 2FA info to it, but I assume other authenticator apps would work fine as well.
Just for reference, even with two-step verification on, you can choose to remember a machine in order to not need it every time you log in. Plus, the point of App passwords is specifically for them to generate a random password for you to enter on devices that don't support 2FA at all, so don't need to worry about needing to make a new password or needing to relogin every time.