The inability to find installed programs by name is laughably unacceptable. How they continue to push this stuff out is amazing, their management must be really awful.
You might also like http://www.getwox.com (basically Alfred for Windows) which can also search the Everything DB.
There’s also stuff like https://mobile.jam-software.de/ultrasearch/?language=EN and https://sourceforge.net/projects/swiftsearch/
Yeah, Cortana is awful and if you totally remove it, you break the start menu (just like removing IE back in the day...sigh). Blackbird can stop the Cortana stuff from loading, though: http://www.getblackbird.net/documentation/
I highly recommend Blackbird for stopping Cortana and the other stuff it does (telemetry / tracking blocking + stopping W10 mandatory updates). I basically run this + https://www.oo-software.com/en/shutup10 on new W10 installs at minimum. https://chocolatey.org is also a big improvement for Windows if you don’t already know about it.