There was a time, in the us at least, when there was private services for things like fire fighting...the fact that governments supply this service at high cost under monopoly conditions and accept payment only in paper does not intrinsically make the government useful or irreplaceable.
You picked a particularly terrible example. Under this idiotic regime, hose connections were incompatible, because they were proprietary, and when a particularly large fire would have required the assistance of other departments, they were unable to do so because they couldn't even connect their hoses to the hydrant at the scene of the fire.
Sometimes, these fires were started by "uninsured" houses. Because they hadn't paid for the service, of course, the private service wouldn't come to their assistance. So when one of these went wild, you could very well end up with your house burned down even though you had paid for the service, because your neighbor had not. And when the fire was particularly large, other local fire services with incompatible equipment could not assist. (Actually, to some extent, incompatible hose couplings still exist, mostly an artifact of the past situation, but FDs generally cooperate to have adapters available when this arises.)
So in such a regime, I could have fire service, but my neighbors could not, and my property value would still be substantially damaged if neighboring homes burned down, blighting the neighborhood. This is assuming my house doesn't end up burned down itself because of the fire spreading from unprotected houses. To get the full benefit of such a regime, I would have to pay for protection for all my neighbors, clearly unfair to me and probably beyond my means.
This is why things like fire protection, police protection and national defense are considered "public goods." There is no way to exclude someone who refuses to pay from, for instance, being protected from foreign invasion, so someone able simply to refuse to pay would be a free rider on the generosity of others. Conversely, the refuseniks in a fire protection regime cause damage even to those willing to pay, who then do not receive the benefit of what they purchase.
Despite the fact that the cost is modest for a reasonable level of fire protection on the individual level, it would be priced exorbitantly if a single or a few individuals had to foot the bill for the protection of all, which is necessary for any effective protection.
I have never seen a rational response from a libertarian extremist as to how to address the public goods problem, or how it would be a good thing to let entire cities burn to the ground because of the refuseniks, who presumably would have these very extremist libertarians among their number.
