But instead it's "when I write an email to someone, the software looks through every person I've ever corresponded with and suggests an email from that list". The 1983 version of that was waiting 5 minutes for a bounce because you typo'd the address. Now it's taken care of for you in a few hundred milliseconds. Not that bad.
As for autocomplete being slow... there isn't really a good reason for this. I've seen PHP apps that add a solid 100ms to every request because they are built in the one-process-per-request model, and the framework does a lot of setup and teardown for every request regardless of whether or not the request uses those resources. Obviously, don't do that. There is no intrinsic reason that "AJAX" apps need to be slow -- you can do a database roundtrip in less than 10ms. Websockets and HTTP/2 eliminate TCP setup/teardown overhead.
Things could be faster, for sure. How much extra would you pay? Most customers wouldn't pay extra for a faster app, so apps aren't faster.
As for why people make mouse-based apps instead of TUIs... it's because the average person has to interact with tens or hundreds of pieces of software on a daily basis these days. If they all work differently, people will never use them. They ask for and prefer fast to learn but slow to use. So developers build on a common set of idioms, even if they are slow in the long run. You'll note that "power user" software is often hard to learn (think Emacs, Vim, Blender, Solidworks) but quite efficient once the user has been trained. People aren't interested in doing that much work these days.
Finally, business processes account for a lot of this stuff. I've been to stores that use a nice efficient TUI for their in-store pickup. But my question is: why is software with a UI even involved? You should scan my order number barcode, scan my driver's license barcode, and then hand me my merchandise. (Why even scan my driver's license. Just eat the fraud and save me 5 seconds! That's a business decision, not a software implementation quirk.) Having to navigate around to a bunch of fields and manually type that information in isn't efficient. The UI shouldn't even exist.