That's not true, the start menu tree was usually relatively clutter-free until the XP era, where companies went absolutely insane and started putting things like manuals and links to the website inside of the start menu tree... yuck!
Also, back then Windows came not only with printed manuals, but also with an actually useful help system and not one that just makes a Bing search.
<Windows>+R, then write "calc", press <Return> and you'll be ready to use the calculator. Very intuitive.
A pretty desktop background and a prompt would go a long way.
I'm now picturing something like ChatGPT (or a specifically trained model) integrated into the shell, so a user can simply type / vocalise what they are trying to do, without knowing specific app details, rather than having to navigate a bloated UI.
Also, there is also a "discoverable" way to launch programs keyboard-only: <Windows>, P, A, C (Programs - Accessories - Calculator).
I just really dislike the Windows 10 start menu search. It slows down on random occasions just often enough to be too annoying for me to use, at least on my machine.
It's also a solution to a self-inflicted problem. Super-crowded Start menus were a problem, but not a very widespread one among people who aren't nerds. The Windows 11 Start menu is crowded but largely because it's littered with Microsoft's own apps. If I were to take out Xbox, Alarms & Clocks and all the other crap I no longer bother to uninstall because it's gonna come back on the next update anyway, I could probably use it quite comfortably.
This works on 1% of the cases because MS decided that you want to search the internet.
Not me, I installed 3rd party application launchers on older versions of Windows. Those were nice and lightweight without the slowdowns of what Microsoft inflicted on everyone.
Big lolz.
Typing to start apps is one of those things that separate the general population from nerds.
Nowadays "you", as in "the general population", start an app from a visual shortcut on your desktop, taskbar, or start menu. Same as before.