I would like to see Rebels be a faction that can also spawn during a game if a faction doesn't have a high enough culture level somewhere far from the homeworld.
Of course this wouldn't be the only way to start them as people would want to play them from the beginning also, but it would be a cool option. Large empires with low culture (or a new game option, happiness, similiar to Civilization 5's happiness with related structures and technologies)
The benefit to this is htat a large empire might spawn multiple rebel factions at it's edges, some might get shits in the area, others might be as weak as milities at first. They would first try to capture worlds in the spawning faction, then start operating as regular factions later on. They might also have large diplomacy benefits towards other rebel factions from the same empire, with the ability to merge.
This coudl be a lot of fun. Post start spawning Rebel factions would keep large empires on their toes, needing to spend more money on keeping the people citizens happy. It would make smaller empires more flexible, and give them the chance of coming back if they supported rebel factions in their enemies.
Just having Rebels as different techs isn't really making them rebels, Make them actually rebel.
Other things they should do, their Diplomacy ships should be able to start rebellions in other planets. I like the idea of getting along better with Pirates. How about being able to masquerade as pirates and hit your own friends without starting a war? (something you could do in Civilization 4 IIRC) Take their stuff and say "it was the Pirates not me!" (but with the chance of being found out also.
How about being able to start pirate bases similiar to colonizing a planet, you get a portion of the loot, and they never hit you? Or perhaps a Rebel Spy can attempt to blow up a starbase or sabotage planetary facilities, successful missions result in that spy gaining experience (each Faction can build only a limited number of spys based on their spy technology and the spy academies they've built) Related to this, Fleet leaders can be trained and gain skills as they win battles. Planetary governors can also do the same thing(giving bonuses to planets and their wells), But the higher level governors might be more likely to rebel (they want a peace of the pie)
I would like to see Loyalists get new skills also, Spy insertion corvettes that let you look at what's happening on a foreign planet (even a pirate base) or star base perhaps,
Observation stations that give you more info but are cheaper than starbases, various technologies to keep the civilians happy, from gladiatoral pits to ballet theatres depending on race. (as examples)
Happiness as a new game system would add to the depth of the game. Some planet types would just be better to live on and have happier people (it's nicer to live on a Terran planet than on an Asteroid for example)