There's an implicit assumption in most of these discussions that beating Google Search is a matter of money and scale, and while there are some evidence for that (e.g. unreasonable effectiveness of having lots of data), it is not a certain conclusion, it is only a conclusion if your goal is to beat Google by making an incrementally better classical search engine. It is indeed hard to beat something by offering something "about the same", when the cost for the consumer is already effectively zero from a monetary perspective.
But this doesn't rule out someone coming up with a disruptive, radically better search. Take this as a thought experiment, somewhere out there, is another Albert Einstein, working on his magnum opus, an AGI based search engine. He has a mind blowing advancement in AGI, like GR was in Physics, that will completely eclipse classical search AND deep learning approaches AND he knows it.
Demos shown to investors are mind blowing, and he quickly raises enough funds to launch a competitor. There is whisper and talk all around the valley. Google tries to make an acquisition, but he and his investors turn it down, because they can see how valuable the tech is. By the time Google realizes their offer should have been much bigger, it's getting traction and taking off like a rocket ship. Now Baidu, Tencent, Alibaba, Amazon, Microsoft, are all looking to acquire it.
Yes, there are arguments that being the "default" is hard to dislodge. But Chrome dislodged IE. Google Search dislodged AltaVista and Yahoo. iOS and Android dislodged Windows. But better technology if it is better enough and marketed correctly can convince consumers to switch. Remember, Chrome was fighting a common refrain that "browsers are done, and who needs another browser?" Efforts like the Chrome Comic Book (https://www.google.com/googlebooks/chrome/index.html) and eye-catching early Chrome ads (https://www.youtube.com/watch?v=nCgQDjiotG0) was able to overcome consumer inertia of having IE pre-installed.
When the iPod, and a rumored Apple Phone was proposed (but before it was first demoed), we had the same naysayers claiming that a new upstart in a space they had never been in before couldn't possibly defeat the established players like Blackberry or Nokia.
But if you create a sufficiently, radically better product, you in effect, create an entirely new platform or market, NOT simply a competitor within the existing market. This is what any hypothetical competitor to Google Search has to do. They need to change what Search means. It can't mean SERP and PageRank, there are marginal gains to be had. It has to be a radically different kind of search experience.