My assumption was that I had to make changes on the core site for all the sub-sites to receive the changes. I didn't realize that making a change on a sub-site would affect all the other sub-sites.
Basically, all it does by default is store the menu configuration in one network-wide DB entry and have all sites read/write that entry. The main site doesn't get any special treatment.
On the other hand, if you change "Multisite settings" to "Per-site", each site gets its own DB entry (created on-demand).
Another question: If I have subsites A, B, C, D and I globally remove a menu item on site A, it will also hide it from sites B, C, D. If I change the settings to allow site-by-site config and re-enabled the menu on site B, is the result that sites A, C, D only have the menu hidden?
Not quite. Sites that don't yet have a site-specific configuration would fall back to displaying the default, uncustomized WordPress admin menu, not your global menu configuration.
As a result, after you switch to per-site settings, the sites A, B, C, D will all show the default WP menu. If you then change menu settings on B, those changes will only apply to B and not any other site.