In regard to Truce amongst Rogues, i would suggest toning it down from Neutrals being completely neutral toward the Rebel player to Neutrals being partially neutral toward the player. I mean lets say half of the local milita would ignore you, while the other half will attack you as any other player. You will still be at advantage, as you wont need that many units early to beat the militia, but you wont be able to colonise shitload of planets so fast as you can now, which i suppose is the issue here.
Alternatively, make the Ice planet/Volcanic planet colonisation technologies in the research tree more expensive for Rebels or move them slightly higher (require more labs).
I was playing today myself against AI as Rebel and paid closer attention to their tech trees. There are certain things i do not know, how they work....
so you can ally with Pirates, right? What does that exactly mean? That they will periodically attack from the moment you research the tech only the enemy players?
other thing, the final diplomatic tech, Liberated something. It says rebel forces will mass at your capital planet or something along the line. Do they count toward your cap? Can you control them somehow?