[damieng]

"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.

[damieng]

https://youtu.be/rf5o5liZxnA?feature=shared&t=542 has a demonstration of NextStep 3 (released September 1992) that clearly shows a computer icon that Steve refers to as "My Computer" and then moves into hitting the "Network" icon globe that shows other computers on his local network.