Reunification of a shattered empire does make for a very good backstory. You get to have various factions and such, rather than different species. Maybe even some procedurally generated factions based on a pool of various traits, so each time you play you'll have different challenges popping up to add flavour. A good bonus-negative balance system could do interesting things.
One game you may have a large number of factions with a "reunification" trait, which makes expanding the empire easier, but it becomes counter balanced by "Anti-technology zealots" who cause havoc with internal affairs.
Another game may have a large number of isolationists or small confederations who will resist your efforts.
Another different option for a storyline is 'convergent evolution', A dozen or so 'classes' of species emerge across the planets involved, and they're designed with characteristic traits to a class along with cultural traits picked from a pool. Possibly a multi level system, so you have a top level "Humanoid"/other classes, then mammal/insect/reptile sub-class, and then cultural traits.
The system could then spin you out a "tentacloid" reptile with cultural trait of religious next to the planet of "giant" mammal technophobes. Class and sub classes would be obvious from basic orbital probes, but all the cultural traits could take longer to discover, and some combinations may even result is 'total war' as the only option. Wipe them out/forcefully subjugate the planet's population or try to ignore them and just go around.
Also, I think that the "Small empire" of a handful of planets opposing you at one time is a good thing for game play. If it is never more than one planet who would oppose you then the game becomes simply nibbling away at the problem. Nothing really opposes you throughout once you establish your initial solid base, and you risk game play devolving into "Which bite do I take next" rather than "Which war to I gamble/risk next?".