How about a great person that can convert barb camps into CS's? In addition, add the chance that an undestroyed barb camp that survives for 'x' long becomes its own CS rather than just continue to pump out higher-level barb units. Barbarian knight and musketmen!? Better to just go into advanced independence route with them I think.
I have also thought Barbarians should eventually become City-States, especially when finding a camp on an island by itself with 5+ units wandering around. (Also agree Barbarian units should be unique; I’d say starting around the Medieval Era.)
However, I think Barbarian started City-States should be unique to regular City-States, retaining their Barbarian style. Not being peaceful like other City-States. Their units still pillaging traders; pillaging improvements; attacking units that 1. attack them, 2. are within X tiles of their borders; condemning religious units; holding rock bands hostage; etc. These actions, when successful, could be how these Barbarian City-States develop.
Envoys would never lead to suzerainty per say, but each level could decrease the hostilities they take against you:
1) No longer pillage your improvements
3) Won’t attack units unless on or in their border (Barbarian City-States can’t close/control their borders like normal City-States)
6) Won’t pillage your traders, and you can send trade routes to the City-State (high gold yield, maybe an Amenity for the city your trader originated from due to black market goods)
If you are the would-be Suzerain you can levy their units to attack a Civ within X tiles. No control over them, just hired guns, may or may not get your money’s worth.
Would-be Suzerainship can’t be seen unless a Civ has a Spy their.
Declaring war on one of these City-States would be similar to a Barbarian scout making it back to its camp; they’d start to produce more units and put up a legitimate fight, just like all well established Barbarian cultures did.
Could easily come up with a half-dozen well known Barbarian City-States, each with its own unique perks, maybe only some provide an Amenity from trading with. Nassau (port city of course) stronger (pirate) ship units that have a chance of commandeering your ship like a Sea-Dog, so on and so forth. Wouldn’t need a lot of variety, but a little would be awesome. Maybe make it dependent on the era it becomes a City-State and only have one per era so you don’t end up with 5 in one era because of a slow exploration game.
Final note: would need a way to make it so you can’t just sit units around a Barbarian camp and purposely let it survive until it becomes a City-State.