"NeXTStep had its Dock, but that doesn't have menus or a status icon."

NeXTStep not only had menus but tear-off dockable menus/sub-menus that are superior to any menus we have in apps today. It's clearly present in the screenshot I linked to.