The best way to compete with them IMO is to choose a slice of queries that they perform very poorly at (like non-SEO spam results) and build something 10x better. But that brings up the challenge of getting users to remember to come back to your search engine.
It's tricky for sure, with no clear answer. But for the first time in a long time, I sense that we're approaching a tipping point for Google's dominance over the web.