Setting up the peering replication and nameservers around the world is considerably harder, but it's definitely not a $10 billion+ problem (the current value of registrars and certificate authorities.) A startup funded by YC could handle that easily.
Dealing with all the companies trying to sue you over others squatting their domains and having to decide who has the better claim would be the most expensive part.
I really hate to say it because it's so cliche and overused, but a blockchain-like system could remove the central authority, the server costs, and the lawsuit risks. But it would introduce concerns over trust, most likely.
The really hard, unsolvable part is the unwillingness of the browser vendors to support an alternative domain name system. If Chrome, Firefox, and Safari all supported a new TLD outside of ICANN's control as a public service (let's call it "Let's Resolve" which would offer free domains and would be funded through donations), it would be very successful. If even one of them didn't support it, nobody would ever consider using it for their websites. Browser extensions, even if they allowed access to intercept domain name lookups, would not work. It would have to be supported out of the box in every major browser, and well, good luck with that. Anything failing to herd those three cats right out of the starting gate is absolutely dead on arrival.
Who knows though, maybe they'll raise .org prices just a bit too much, and piss off an established non-profit enough to start a huge campaign to create an alternative. But probably not.