Watching Crimson Echoes, the team there postulated(there's a word I don't get to use often enough) that the Gates were made at certain points(starting with Crono at the Millennial Fair) throughout time and progress through the timeline at the same rate as everything else.
To use the example from CE, when the year 1005 came, they could only travel back to 605 A.D. or 11995 B.C. rather than 600 A.D. or 12000 B.C.
However, and please correct me if I'm wrong in this, because I'm nowhere near as versed on this subject as other Compendium members are, I think that the Gates were created by the Entity at the start of the game, i.e., when Marle is sent back in time and Crono follows her.
My backing for this is that the rest of the time stream is unaffected by the workings of the time travelers(unless we're assuming some kind of causal loop, but I don't want to get into that).
Throughout the story, Chrono & the party travel through hundreds, thousands, and millions of years. however, there is a paradoxical sense of a linear progression of time in the story. for example, when you take the gate or epoch to 12000 bc, you dont always come out at the same moment as the first time you arrived. after the fall of zeal, the gate doesnt still take you to the time before the fall. so in spite of the time traveling, time seems to move forward normally for the time travellers.
Looking back through your post now, I feel I might've missed the point of this paragraph. The time travelers are unchanged by the progression of time due to Time Traveler's Immunity(TTI). The Chrono Compendium's encyclopedia has an article on this...somewhere.
As for the time egg used on Crono, they simply removed his death from the timeline. Since he had time traveled before, he was immune to the change in the timeline caused by his being resurrected, if that's what you want to call it.
Here's another way to think about it, to use your example of Magus's warp:
Let's say the events in Magus's castle took place on July 8th, 600 A.D. The gate caused would have sent Crono's crew back to July 8th, 65,000,000 B.C. and Magus back to July 8th, 12,000 B.C.
Time progress the same through all eras, so when Crono's gang found the Gate leading to 12,000 B.C. under Tyrano Lair, on, let's say, July 11th, then those three days passed in 12,000 B.C. as well. They passed through the portal on July 11th, and made it to 12,000 B.C. on July 11th, and Magus had existed in that era for those three days as well.
Of course, this is all still assuming that the actual time travel takes zero time, but I digress as I don't want to make things too complicated.
Ok, I think that's everything. If you find some fallacy please correct me, and I hope that it clears things up if I am correct.