Agreed. In order for government to exist and function, it has to have some basis of revenue. While the "voluntary" basis sounds nice, in practicality what it turns into is the classic "not in my backyard" argument: everyone wants the benefits but doesn't want to pay for them.

Take fire suppression for example. What about if a fire starts in one area which isn't covered? Are you going to refuse to fight it until it has crossed over and started harming an area which is covered? By that time it can be out of control!

Police action (I don't use protection as that is nonsense: police don't "protect", they only act responsively) is part of the executive power vested in the State during its creation. Simply agreeing to be part of a civilization both entitles you to call on the police in the event of an infringement of rights, but also burdens you with the financial obligation to provide for the funding of the police.

Military. The police are for maintaining internal order. The military is strictly for defense against external enemies, but is also a contractual provision within belonging to a civil government.

Utilities (water, sewer, power, etc.). There is no governmental mandate to provide for these services, but there is a case for efficiency and consolidation in monopolistic service due to infrastructure needs. Because of the physical size of the facilities and service needs (pipes, etc.), it makes practical sense to have a single entity responsible for servicing a given area. But because of the inherent dangers in monopolistic endeavors this is dangerous all the way around. If it is run purely by corporate entity, there is nothing to stop them from charging rates that would drive out many potential customers. If it is run by the government, there is the real challenge of innovation. Personally, I think the public utility model has been working very well and is probably the best option.

Data/Communications. This one is is a mix of a utility model and a conventional business enterprise. Again, there is the aspect of the physical infrastructure (and don't get into the wired vs wireless with me - either one is still taking up valuable real estate) to take into account. The investment needed to bury cable is significant and requires very real coordination and government planning to effect. But the actual provisions of the communications service are significantly more fungible. For this one, a base of a public utilities model for the infrastructure appears to work well with the access to that infrastructure being sold at the same base rate to any potential corporate competitors so they can turn around with service offerings.

I know that Objectivists like the minimal government approach, but sometimes I think they can get carried away with it...

"Public" in this sense means "non-excludable", meaning you cannot provide them to some and not others. Police and military are non-excludable, but fire is excludable.

People will have different ideas how the level of policing and military they want. But once we deploy a police force in an area, everyone in that area gets the benefit whether they want to pay for it or not.

The fire department and private fire fighting services, if they existed, could easily provide their service only to paying subscribers.

So in my view an objectivist society would have no fire department. Policing would partly provided by people protecting their own homes and their neighbors', if they're so inclined. They would still need police and legal machinery to catch and prosecute criminals. Military would partly provided by militia, but they would still need some kind of a minimal standing army. I'm intrigued by ideas of how to fund these non-excludable services without taxes, but I do not know how that would work.

While I am all for a VERY Limited Government, I firmly believe that some essential services should be provided by the Government. The ones listed above are a good start with a few limited others as well, the highway system and roads for example.

Some might reasonably argue that the highway system could be privatized and while this is true the highway system is a Critical system in a defense scenario so I will continue to argue that it should be handled at a Governmental level..

So that leaves the question as to how these things are funded. The obvious answer is by taxation. Local things such as Fire and Police should be funded by local taxes based on property ownership. Where as National level things such as the Military and the Highway system should be National level taxation.

Ideally the taxes required by ALL entities combined should be 10% or less. If 10% is good enough for God it should be good enough for the Government.

This question conflates two kinds of service. Two of the services the question named, are proper core government functions anyway. I refer here to the police and the military. Concerning taxation, Rand said people would pay for these in the same manner in which they bought insurance. The heaviest stakeholders would pay the most. And a property owner or tenant would receive credit for defending himself and his property--hence "militia."

(The anarchist solution is, of course, more extreme. Some anarchists refuse to believe a society has any enemies beyond what one makes. Laying aside this Pollyanna-ish version of irenology--the study of peace--most anarchists who really think about the subject, suggest forming Committees of Safety, consisting of the major stakeholders. John Galt, Francisco d'Anconia, and Ragnar Danneskjöld functioned as just such a Committee of Safety. John acted as the proxy for Midas Mulligan; Francisco and Ragnar acted each in his own behalf.)

She also suggested simply using the lottery to pay for these things.

Fire protection is another matter altogether. I'm sure people would buy fire insurance, and the insurance companies would hire (or form) the fire brigades to put out fires whenever they started. It might even behoove the fire company to put out a fire even in an "uninsured" dwelling--so the fire would not spread to other dwellings. Then they would lay an assessment against the owner of that dwelling. The legal theory of the "injury in fact" would be this: the householder let a fire start in his house, and never let an insurer inspect it for fire risk and so on. As such he posed a danger to paying policyholders. The fire brigade had to act. Now someone has to pay for the fire brigade's extra work.

Schools should never be a government service.

"Utilities" should never be public, either. Let every householder choose whether he wants to connect to, say, a gas pipeline, or order in a tank to hook up in his back yard. Let them decide whether to draw their water from a well or connect to a pipe. For the electrical grid you have the added complication--which a private grid could handle--of people generating some or all of their own electricity. This applies equally to industrial cogeneration as to a householder installing a solar battery or a wind turbine on his dwelling or curtilage. ("Curtilage" is legalese for "yard.")

Who was it that rescued Galt from the State Science Institute in Atlas Shrugged? A citizen's militia from The Gulch.

Involuntary Taxes (at least for Police and Military, not so much for firefighters). Ultimately there is no other way.

All taxation is backed by the threat of Lethal Force. Is it OK to threaten someone's life and take their money to protect the country as a whole? Yes, but barely. The consequences of letting anyone and everyone opt out of this specific case far outweigh the consequences of bringing lethal force against various individuals for the protection of everyone.

Is it OK to threaten someone's life and take their money to mandate that firefighters will protect their house? No, not even close.

I think it was John Hospers who suggested charging a percentage of contracts signed if you wanted the agreement backed by the courts. The fees would cover police and fire departments.

I know that I would voluntarily pay for police, fire and military. If I didn't like the job they did, I'd stop paying.

I recently heard that it took 30 years of legal wrangling in order for Americans to be allowed to start homeschooling their own children. Frankly...that fact scares the hell out of me...

I like that idea...

Why would you look for a non-government military? Protecting its citizens from aggression is the proper function of government.
After government is restructured to remove today's corruption, its proper military function would be paid for by owners of property who would want protection from invasion. Rand envisaged a voluntary funding system in place of taxation. She obviously did not use this phrase, but today you can imagine a type of "crowd-funding" for defense. Wealthy people automatically pay more because they have more to protect, a bit like buying insurance (wealthy people voluntarily have a larger insurance bills).

That makes sense for education and fire but police and military must retain the potential for use of force, even deadly force if they are to be effective against a determined enemy. Short of hiring mercenaries how is this done? For example, if the Gulch was invaded by a hostile force intent on destroying the colony what wold be an appropriate response and how would the costs be borne?

I am far from an expert, and better minds will answer your question, but I do know that a purely Objectivist society would have limited government.
Did you know that in very early days in America, a person purchased fire protection if they wanted it. If their house caught fire, the company would come to put the fire out. It was a private enterprise.
Remember that education was never meant to be publicly funded in the US.
Just a couple of examples.