Maybe instead of a new nav menu interface the (hopefully) more solvable issue of wp_nav_menu() using so many database queries can be looked into. I can count 6 queries added to any page using that function just for a simple list of menu links.

Fixing this and even some other quirks would be on the level of the just awesome Date/Time improvements that came in WordPress 5.3. That made the dates system way more solid and a joy to work with. I think these are the kinds of fixes that could get many people excited among the otherwise massive changes regularly added with the editor.