Thanks, I think your questions are important, because those are the exact questions people often ask when presented the idea of private protection agencies and other libertarian ideas. So I'd like to address them and maybe try to demonstrate that those ideas would indeed work (so please let me know if I managed to convince you at least a little bit).
>Similarly, if you dislike the service of your private protection agency (which is still a government, just not monopolistic), then if you stop paying you'll just end up dead, unless you can pay for equivalent protection from someone else.
So, at the very least I already have a choice between one protection agency and another. If one promises to kill me if I cancel my subscription, I simply go to another agency that will be happy to have my money and ask them to protect me against the one I dislike. Because both agencies are in the business to make money, they realize that violence is more expensive and nothing happens.
Then people would usually say "But what if two agencies form a cartel"? Well, in that case, nothing really prevents a third agency to spring up as a competition and take customers away. Historically, cartels break down very fast without any intervention because one of the cartel members usually breaks the rules or an outside competitor emerges. Also, intimidating even one customer because he decides to unsubscribe is very likely to cause a chain reaction where a company simply loses its business.
A cartel, though, is still a better situation than a government. If a cartel decides to kill or detain anyone who's not paying, it cannot actually claim, like government does, that it's a legitimate action, because people would take it for what it is - a violent action by a criminal gang. A great majority of people would be very likely to at least stop paying the cartel as soon as they realize it doesn't do them any good and some violent resistance is also very likely. A cartel is in the business of making money, thus it is in its interest to make more money and attract more customers. They can't print money, nor can they steal without losing a lot of customers.
>if like me you find it distasteful that the US can abuse its economic power to trample people in other nations around the world, how do you tolerate the idea of billionaires doing whatever the hell they please
Billionaires can't really do what they please to the extent a government can. First of all, any violence that is likely to happen would be paid for out of this billionaires pockets. Governments, on the other hand, don't pay for violence. They steal money from taxpayers, then use these money to finance wars, steal more money and indoctrinate people, convincing them that what they do is not actually theft.
I don't really see rich people starting wars or intimidating other people. Why? Because it's a costly activity. Creating actual value is profitable. Inducing violence to steal money is only profitable when you can steal more than you spend in the long run.