Ironically enough I think it is actually too early. I think we would get more bang for our buck if we did that after some military campaign and our soldiers melted back in to the population. That way there is synergy.
Also having some military background is a must. Almost all movers ans shakers of the Rome had military at their back. The likes of Cicero were Legends of their own right but despite that without military they could never stop the likes of Ceasar.
So we should probably go with military enough so when we start political manuevaring we don't get hammered by it.
Also Slave rebellions are not good enough to get a thriump but it might get us a Ovation which would look real good on our resume if we decide to go for Striped Tribune.
You're not going to get as much of a synergy boost there as you're thinking. Roman soldiers at this time are drawn mainly from the
capite censi, who are essentially utterly disenfranchised, in practice if not in theory. (And if we're in a position to endow them with sufficient wealth and property to move up to the Third Class or higher, then pretty much by definition we have a huge electoral machine already.) Now, they're not entirely useless - they can talk us up and, if worse comes to worst, we have a ready made street gang. But civilian clients can do the former across a broader swathe of society, and the latter comes with a host of attendant problems.
Now, while we're on the topic of synergy, I'd like to talk about how Advocacy synergises with Never Too Early. Advocacy is explicitly looking for the less prestigious cases to raise our profile. Those cases are going to involve the exact same class of people we're going to be targeting with Never Too Early. Which means that we're going to be winning prestige and clients at the same time that we're going to be building an organisation to harness our existing prestige and clients to win
more prestige and clients. The more clients we have and the greater our reputation, the better the cases we can take on, etc. etc. They feed into one another very nicely, IMO.
As for the military background, I agree. We need one. But we're inevitably going to have one, because we're going to serve in ten campaigns before running for Quaestor, as is required, and we're a good enough soldier that we're going to get something out of it. I would just like to have a large enough network of clients established that people remember our name when we get back to Rome after our military service. (No point in doing great deeds if no one ever learns of them).
As an aside, we're definitely not going to win an Ovation with Slave Rebellion. Even if such honours are awarded for such a minor thing (they're sending out a militia rather than the legions), we're not in command. Young Marius is.