You will need data on relevant results for a broad swath of queries to fine tune your ranking models against, and will need to spend millions on infrastructure just to crawl and store an index of the entire web.

Wouldn't there be a ton of search startups if it were actually this easy?

It's not so much the difficulty, though yes it is hard, but it's generally extremely difficult to raise capital as a late entrant into an established industry. Unless there's something disruptive. That said, it doesn't take that much capital to build a new search engine with today's computing infrastructure so a few have tried over the past 5-10 years but none were as good as Google (a minimal benchmark). They found a lot of initial interest then died out quickly (sorry I'm forgetting the names, maybe Powerset, Blekko and another). Without doing any "heavy lifting" and also thus not requiring much capital, these so-called "private" search engines have gotten some traction.

I think competing with Google would actually be a more difficult problem

The only honest answer to that question depends entirely on one's interpretation of the strong efficient market hypothesis.