A new type of independent people: nomadic tribes. Unlike independent cities, between the ancient era and including the Early modern era (like the  Kalmyks), independent people can spawn from the nomadic list. They will hold a number of open territories (based on map size?). They have a different set of treaties focused on mercenaries with a nomad-like ability (can't build outposts) and trade. Especially having a merchant like ability to trade resources from other empires when trade routes go through their territory or they border. Razing an outpost can be high reward, but spawn enemies.