Provide legal and monetary incentives to form cooperatives and associations instead of corporations. Then, when people are used to being active parts in such cooperatives and associations, progressively allow associations to replace some of the State's functions.
If you just make the State disappear today, you will not get anarchy, you will get chaos. Self organization doesn't magically appear as the state disappears, it is built over time. And there can be many different outcomes, including a lot of bad ones. The State should gently steer people towards a fair organization by ensuring that such organization is already there before it relinquishes control. Of course, this is the dream of Communism, and we now that the State rarely does that even when it promises to, but still, I believe it would be a good intervention.
I agree that we cant kill the whole beast in on shot. However, this might happen due to natural consequences when it collapses in on itself. A gradual closing down is much preferred.
As you and I both know governments generally don't shrink unless forced to. So expecting them to gradually scale down probably wont happen. I suggest starting with the war machine and working your way towards welfare programs and then the taxation system. Closing down everything except the police over a 10 year period.