There are some great ideas here. Here is my take:
1) I like the idea of using mid-game settlers as colonists. This should be a new technology that: a) replaces Settler with Colonist, b) colonists make cities at Pop 3 with a handful of pre-existing buildings, and c) are Puppets by default.
2) Puppets/Colonies can be Annexed at any time.
3) Puppets and Colonies both have the City State like tracking bar. At the most loyal level, you get the benefits like you do now with Puppets (or more). As loyalty decreases you increase the risk revolution. Cities in revolution increase the likelihood neighboring Puppets/Colonies join the revolution.
4) Puppets/Colonies revolt for a set amount of time. (Maybe a revolutionary Great Leader unit spawns with a number of fighters. You gotta take out the leader.) Revolting cities cannot be annexed. If the player/AI fails to quell the revolt in the specified timeframe, the cities form a new civilization! Oh snap!
5) Losing ones original Capital risks sparking a revolt.
6) Spies can be used to start revolts in Puppets/Colonies.