> Probably the best thing Microsoft could have done back then was make a little pseudo-video† walkthrough, showing people what's in the Start Menu and what happ

> Probably the best thing Microsoft could have done back then was make a little pseudo-video† walkthrough, showing people what's in the Start Menu and what happens when you click on a few of the items in there. They did that. Windows 95 came with a whole bunch of tutorials. IIRC they worked like you describe. There was also the notorious "Tip of the day" via the welcome.exe.