You guys talk and talk... In the end, the solution is SO simple... give CS a wall from the start !!! Yes, if you wanna protect them in the end game, you WILL have to take action, but at least at the start of the game, it will become quite difficult for the AI to capture one...not impossible, but very difficult !!!
Hmm, if you need to get rid of a cs you now have to wait.. just because some players want to put envoys in them. The city state suffers because it doesn't protect itself, the core design of the ai and how it protects or attacks is a known issue, the problem is compounded by limited resources. No iron, no swordsmen, no horses, no knights and so on.
Maybe a way of safeguarding the cs would be to give each one a unique entry level unit, that handles both melee and ranged fairly well. Maybe some sort of Royal Guard, which makes it overpowered. Then remove the ability to levie the units. Or at least, the RG units. You could maybe do this to Cs units only, making the first 3 units op, giving them a special buff that isn't available elsewhere. Enough to allow it to one shot most ancient and classic era units. But still weak enough to be killed if needed.
Or alternatively a minimum period at the start of the game, when noone can declare war at all. Allowing ai to build up some forces. Since players also use the lack of ai forces to quickly expand by caputuring their cities in early game.
Or code the ai to protect city states as an extra default trait. Then anytime anyone attacked one, you would face condemnation from all the other civs and likely several battlefronts as they all tried to recapture the cs to liberate it.. a sort of cross the board emergency from r&f.
In the later part of early game I usually have 2-3 cs's with about 20 units.. by mid game the cs and the ai in general tends to disband it's armies. Probably to free up building support economy. This kind of thing could be removed for all cs. Maybe halved for the ai, then you'd maybe see midgame and late game civs actually have an army.
This also spreads out into a general ai issue, so maybe work needs to be done to balance it. In civ 5, if you attacked a "protected" cs, the protector nearly always declared war on you. And instead of ai's just denouncing you, they should maybe have different versions of denouncments, ie maybe a diplomatic denouncment which is a general level of disgust at something you've done and then a military backed denouncment, where if you don't cease and desist, it will lead to war.
If players had to face 8-12 ai's all telling you to backoff from city state conquering or you'd face their combined might.. it might give some pause to continue and this also follows for other ai's.