Turns.
ThorHammerz forgot to mention one additional factor, and that's "Great Person Spawn Bias": the first Great Person you get from a city-state is generated twice as fast as the others.
The instant you adopt the Patronage finisher, it will generate a random number of turns based on the formula ThorHammerz mentioned; the first time this happens, the Great Person you get is generated twice as fast. The game will then decrease the counter by 1 each turn, regardless of how many allies you have, until the counter hits 0, at which point a random allied city-state will gift you a random, non-prophet Great person and the game will regenerate your turn counter using the mentioned formula. Spawn times are increased and decreased with game speed, so they'll be more frequent on Quick and less frequent on Marathon.
Gaining new allies decreases the turn counter by 2. Losing a city-state ally does nothing. Coincidentally, this means the ideal way of generating great people from city-states is to constantly unally and ally them, since you lose nothing by losing a city-state ally but you always reduce your spawn turn count by 2 every time you (re)ally a city-state.