This is my general timeline of events based on a post by @oxmox, with a few changes based on release dates and when characters drop out of certain storylines, with [ ] brackets listing events that happen out of the game.
[Rikti Invasion of Primal Earth / Hamidon War of Praetorian Earth]
0. Original Tina Macintyre and Maria Jenkins arcs (available through Ouroboros)
[A decade or more passes]
1. Goldside Praetorian arcs
2. New Tina Macintyre and Maria Jenkins arcs
[Terra Volta is invaded by the Praetorians and the Freedom Phalanx attempt and fail to defend it]
3. Apex Task Force
4. Tin Mage Task Force
5. Admiral Sutter Task Force
6. Behavioural Adjustment Facility Incarnate Trial
7. Lambda Sector Incarnate Trial
8. Keyes Island Reactor Incarnate Trial
[As the war progresses Praetorians start to leave the city, some fleeing to First Ward with the help of the Carnival of Light]
9. First Ward arcs
10. The Underground Incarnate Trial
11. TPN Campus Incarnate Trial
12. Minds of Mayhem Incarnate Trial
13. New Dark Astoria arcs
14. Dilemma Diabolique Incarnate Trial
15. Who Will Die? arcs (not relevant to Praetoria but are the reason why Statesman stops showing up on the radio during Incarnate Trials, but comes after Dilemma Diabolique as Sister Psyche shows up as a hostage in the Trial)
16. Night Ward arcs
17. Belladonna Vetrano arcs
18. Magisterium Incarnate Trial
[Praetoria is in ruins after Tyrant loses control and Vanguard work to evacuate the remaining Praetorian citizens before Hamidon destroys everything]
19. Pandora's Box arcs (not relevant to Praetoria)
20. Praetoria's Hidden Treasure Villain Tip Mission (Level 30 Villain's lead-in to Mr. G)
21. Provost Marchand (Hero 30+) / Mr. G (Villain 30+) / Sgt. Schorr (Rogue 30-40) / The Major (Vigilante 30-40) arcs (Sgt Schorr's arc doesn't have any Praetorian content in it I think, but The Major's arc does)
22. Number Six arcs
The original Tina and Maria arcs are partly canon, available through Ouroboros as events that happened shortly after the original Rikti Invasion and presumably not long after Praetoria's Hamidon War. Things like Apex, Tin Mage and Sutter TFs I would say take place largely around the same time as each other, much like BAF and Lambda. First Ward is concurrent with the early Incarnate Trials but happens before Underground Trial as you work with Vanessa Devore before she dies in the Underground, Diabolique is released and Dark Astoria arcs start. Night Ward happens after Minds of Mayhem as Malaise is dead in it. Dark Astoria & Dilemma Diabolique happen before Magisterium, as Dominatrix is acting on Tyrant's orders during the Dark Astoria arcs but is captured during. She is rescued in Dilemma Diabolique Trial, then helps out in the Magisterium Trial against Tyrant. Belladonna Vetrano's arcs pick up directly after Night Ward and directly precede the Magisterium. Provost Marchand, Mr G, The Major and Number Six are all post Magisterium and never went live in original City of Heroes, only available on the Test Server before shutdown. All very complicated, but for the most part things happen in order of release date.
For Praetorian characters to experience everything in timeline order they would need to following their Level 20 arcs leave Praetoria to Primal Earth and as quickly as possible reach level 40 then continue with Tina & Maria and become an Incarnate, using Ouroboros for First Ward & Night Ward when necessary. Alternatively for a more consistent levelling experience one could go to First Ward, Night Ward, then straight on to Provost Marchand/Mr G's post Praetoria arcs, having not participated in the greater war as at the time because they were not an Incarnate. Very awkward.