There's a detailed account in your city screen about what exactly causes the problem.
For example, I'm now running a Nightmare game with literally 40 civs on a cramped Duel map (the Space one, lol) - and ONE city is in perpetual rebellion every couple turns forever.
It took me a while to actually have the bright idea to check what causes it - and it's, no surprise, crime.
So one of the most important things you HAVE to do, is to keep track of your crime level and try to fight it as much as possible.
It's annoying, but it's also the major cause for rebellion shenanigans.
Oh, and always have a spare Bard (or a dozen) in your city - this way you can at least eliminate the practical problem of rebellion when it already triggers.
It might be a "cheat", but I'm so immensely glad that I finally know the "trick" of sacrificing an Entertainer to remove the annoyance.
This is SO much better than having to wait out those turns a zillion times.
Still annoying, but at least isn't freezing my game as much (before I knew this trick, I had a game that literally got stuck in perpetual rebellion cycles almost non-stop, that was UGH).
Note after reading it myself again.
I wanted to add that it's not always a bad idea to let a city or two (if you have five or ten, of course) to form a new civ - you can always recapture it, and it may give you new Major Cultures, lol.
I just realized myself that it'd be so much faster to play a single-civ game (on Nightmare, of course) and let a city or two get so bad that they'd want to split off.
So, then let them - and then immediately swallow it back, with a chance for a random civ being of a different Major Culture (not sure if it works, though).
Or, alternatively, you can make that way a list of "civs you met" to be LONGER than 40 civs, mwahahaha.
Funny, I say.
