The thing wrong with writing passwords down is that writing passwords down makes 2FA into 1FA. A password, when stored outside of someone's head, is a token, not a password.

If you really do 2FA, though, you should actually relax your password requirements. The most important attribute of a password used in a 2FA scheme is memorability, to make sure the user doesn't write it down (and thereby remove a factor.) Even a dictionary word works, as long as it's not one that's written down on e.g. the user's employee profile, like their mother's maiden name. Generating one or two dictionary words would be fine.

Keep in mind, the majority of 2FA security is in the token. As long as you verify the token first, the only power the password needs is to distinguish the device owner from someone who stole the device, or has snuck onto it. It doesn't need to protect against automated attackers; that's what the token (plus rate-limiting) is for.