Does menace require that both blockers be able to legally block the attacking creature?

Menace states that a creature with menace can't be blocked except by two or more creatures (CR 702.111b). Critically, this modifies the legality of the block itself — it doesn't just require two creatures to be assigned; each of those creatures must individually satisfy all normal blocking requirements as well.

Normal blocking legality (CR 509.1b) requires that each blocker be able to legally block the attacker on its own merits — no 'flying' if the blocker lacks flying or reach, no blocking if the blocker is tapped, etc. Menace adds an additional constraint on top of those existing rules: you must gather at least two such legal blockers, or the block cannot happen at all.

So if only one creature in your available pool can legally block the menace creature (say the attacker has landwalk and only one blocker is unaffected), you cannot block it at all. You cannot 'pad' the block with an otherwise-illegal blocker just to satisfy the two-creature minimum.

Concrete example: Your opponent attacks with a 3/3 creature that has menace and flying. You control a 1/1 Bird (flying) and a 1/1 Human (no flying). Only the Bird can legally block the flier. Because you cannot assemble two legal blockers, the menace creature is unblockable in this situation — the Human cannot be used as the second blocker to satisfy menace.

This interaction is governed by CR 509.1b (blocker legality), CR 702.111b (menace definition), and the general rule (CR 509.1) that all blocking restrictions must be satisfied simultaneously when declaring blockers.