There is a big difference between paying for a service I can get from 5 different providers just in my local area and a country wide monopoly. My main problem with the government is that I can't choose another government where I am, which means the government can be inefficient and unfriendly towards consumer (big public spending, bureaucracy). It's not because of the illusion of being stateless; if nobody protects you, everyone can kill you, as that couple of bitcoin traders found out when trying to setup camp in international waters. It's mainly so that different agencies can compete with each other and so that nobody has a monopoly on violence.

Small independent entities would also have incentives to keep laws and contracts small and short: they can't afford to spend public money to make them and they won't care about victimless crimes like our governments love to do.

Overall, I think we can come with a society that is more decentralised, more efficient and closer to what consumers want.