They are a private company in the sense that they are not a government entity, and thus the first amendment does not apply to them. This is a different sense of the word "private" than whether their stock is or is not publicly traded on an exchange.

What do you do when all speech takes place on corporate-owned platforms?

The nature of the problem (a big monopolist behemoth of a corporation is too big and powerful and lacks incentives to change) and the solution (only state action, regulation, mandates, i.e. something more powerful than Google must enforce Google to act) is by definition a political problem. This is like the epitome of what politics is for.