Part of the reason Rebels were so annoying was because your empire was so big. And there were 20 different countries to fight.
In the (relatively smaller) maps of elemental, without rebels, bandits, and thieves ... you won't have anything to do.
I agree that bandits and rebels shouldn't be a constant pain in the arse ... there should be bandit camps in the Swamps and forests ... where bandits, highwaymen, theives, and brigands are spawned.
For the most part, your units are only in danger if they roam near the bandit camp, but occasionally they could make forrays to destroy your improvements. Or attempt to take a city.
As I said, I've played Rediculous difficulty ... and while the individual Super Power monsters were nice, I feel that the weaker creatures didn't spawn in large enough armies.
I mean, I'd like just 1 super power per 9x9 area ... while perhaps an army of 30 or so bandits or goblins.