I can picture Sonic and Eggman going to the past separately. Sonic kicks Eggman's ass at Metropolis, Eggman escapes to the past in his time machine. To give chase Sonic travels to the pyramid (Hidden Shrine?) next to Metropolis and activates a mystical mechanism there to send himself to the past. He arrives some time after Eggman has set up and started conquering the past. They presumably use the same methods in most eras. Eggman leaves by time machine, Sonic revisits the pyramid to go after him. The fact that dome thingie in the mountains (the Death Egg? or perhaps the base where it's being built?) is in the original present, yet you can see an earlier version of it in the past, also suggests that Eggy had already time traveled before the story began. I imagine they would have used S3K-esque cutscenes and a South Island map ala S1SMS to show what was going on.