The phone company has been characterized many times as a natural monopoly. But it certainly wasn't in its early days. Telephone companies sprouted like weeds and all competed with each other.

I don't know what the interconnection between them was like.

But I can say that in the days before the internet achieved dominance, the various privately operated networks provided gateways so one could connect to the next. In fact, the term "inter"net came from connecting existing networks together.

Lastly, it's not necessary for competing water companies to run parallel sets of water pipes to your home. Your neighborhood may have a communal pipe, and then water companies compete to connect to that pipe. There may be pipes connecting various other pipes. The water companies compete to fill those pipes, or rent access to those pipes to deliver the water to individual subscribers.

I.e. a free market water system need not at all look like the current monopoly utility system.