Another Idea that just popped into my brain is a short possibly animated hologram sequence at the beginning as a prelude to Star Wars.
A bit like the prelude to Lord Of The Rings, explaining the forging of the Republic and the rise of the Jedi.
That way you'd get a feeling of the birth of the Republic thousands of years before the cracks begin to show in TPM.
That would put it's death in ROTS into context and it's rebirth in ROTJ too.
It needn't be anything too elaborate, shadow puppetish would do.
Something along the lines of an early learning hologram for recently child snatched Jedi acolytes.