Adding a search to the start menu is huge and completely changed how I use it -- I almost never do anything besides hit the Windows key and start typing a search query. Besides that, the way nested menus worked was frustrating and I'd frequently waste time doing things I didn't intend trying to navigate them.

That explains it. I use win+R (the hotkey for run) the same way since I think win95.

When I search the start menu, it does the weirdest things, e.g searching notepad via bing instead of starting it, or preferring the uninstaller above the real program. So I learned that the start menu is basically broken for search, and became harder to use as a menu. I mostly abandoned it.

Meanwhile, the gui widgets, built in windows and control panels became much worse and dumbed down. It pretends to be a helpfull assistant, but behaves more like an arrogant drunk. I want to do some work on the machine, not be told about some experience it really wants to shove in my face.

Well, the difference is Windows + R I would need an exact command and the search bar I don't. I share some of your frustrations about the relevance of the top result but still, partial matches are important to me.