One idea I had was to use Dooku and Sidious meeting at the end of AotC:

Phantom Menace ends, either with Qui Gon’s funeral or the giant peace ball. Possibly flip the order of the two somehow.

Dooku and Sidious meet mysteriously on Coruscant. The audience thinks oh crap, who’s this guy. Sidious had another backup apprentice all along and Maul getting killed didn’t end anything. Following right up from “Which was destroyed, the master or the apprentice?” Also Dooku was on some unspecified mission, and Sidious says everything is proceeding as planned, so clearly everything that happened was how he wanted it even though the Trade Federation was beaten. Very ominous.

Next we see Palpatine, obviously Sidious in case the audience didn’t get it before, announcing the creation of an army of the Republic to counter the increasing threats of the Separatists. Maybe include the part with Windu and Yoda up there like they saw this coming.

Shots of the clones on Kamino.

I think this is still missing some connective tissue putting the Trade Federation and Separatists together.