To me, it seems that menus—which are likely to contain navigation—should be handled in the same way as plugins, which have an “activate” and “network activate” options.
Except that not everyone uses MultiSite. And not everyone uses MultiSite that way. I agree, some of us want multiple blogs, all with the same (or VERY similar) layouts and, in that case, it’s a mother to get all your widgets the same on all blogs. In other cases, for example, I run a MultiSite where each and every blog has it’s own design (one garish, one simple, one bog standard, etc). And then there are people who have multiple DOMAINS, and there shouldn’t be standard navs for all of them.
As a sidebar – “network activate” just means ‘This plugin is turned on for all blogs.’ The settings for each blog STILL need to be customized per blog. So … there’s that.
Anyway, my idea about the functions.php is a little unspecific, since it’s theory right now. If you defined your nav menu as a function (li and ul and all via echo) and then called it as an add-action to the widget area, it SHOULD put the code in. Then it’s just a matter of CSS styling. This is all entirely untested, but in THEORY it’s how a lot of parent themes work, so I’m pretty sure it can be done. I’m just not 100% crystal on HOW :/