Shagrat and Gorbag also mention "the Great Siege", presumably the siege of Barad-dur 3019 to 3026 years earlier, though it could something else like the Noldorin siege of Angband.
About SA (Second Age) 500 Sauron becomes active in Middle-earth again. Sauron begins to take control of all orc groups, ending their centuries of freedom from higher powers.
About SA 1,000 Sauron takes over Mordor, begins populating it with orcs.
In SA (Second Age) 3262 Sauron taken a prisoner to Numenor.
SA 3319 Numenor sinks, Sauron's body killed.
SA 3320 Sauron's sprit returns to Mordor and soon makes a new body.
SA 3434 to SA 3441. The Siege of Barad-dur, probably "the Great Siege" mentioned by Shagrat and Gorbag.
SA 3441. Sauron defeated and killed and his ring taken. The Second Age ends and the Third Age begins. The Kingdom of Gondor guards Morder with fortresses.
About TA (Third Age) 1050. Sauron forms a new body. All orcs and other evil creatures begin to fall more and more under Sauron's control, ending about a millennium of Orcish freedom from higher powers.
About TA 1100. The Wise realize that some dark power, probably a Nazgul, has made a stronghold at Dol Guldur in Mirkwood. Actually it is Sauron.
About TA 1300 Orcs and other evil creatures begin to multiply again. The Nazgul reappear and their chief goes to Angmar and becomes the Witch-king.
TA 1636 the Great Plague devastates Gondor.
TA 1640 Mordor is left unguarded.
TA 1975. The Witch-King of Angmar is defeated and leaves the north.
TA 1980. The Witch-king comes to Morder and gathers the Nazgul.
TA 2000-2002. The Nazgul from Morder besiege Minas Ithil, presumably with the help of Mordor Orcs. This may be "the Great Seige" mentioned by Shagrat and Gorbag. Minas Ithil becomes known as Minas Morgul.
TA 2063 to TA 2460. The Watchful Peace. Gandalf enters Dol Guldur in Mirkwood, Sauron leaves Dol guldur and hides in the East, and the Nazgul are quiet in Mordor. (But no doubt the Nazgul boss the Mordor orcs).
TA 2460. Sauron returns to Dol Guldor in Mirkwood.
TA 2850. Gandalf enters Dol Guldur in Mirkwood and discovers that Sauron has returned.
TA 2941. The Hobbit. And also the Wise drive Sauron from Dol Guldur in Mirkwood.
TA 2942. Sauron returns in secret to Mordor.
TA 2951. Sauron declares himself in Mordor and openly rebuilds his power.
The Dark Tower is rebuilt. Three Nazgul are sent to rebuild Dol Guldur.
TA 3018. War of the Ring begins.
TA 3019. Presumably equivalent to SA 6460. War of the Ring continues. Shagrat and Gorbag have their conversation. This is:
68 years after Sauron openly proclaims himself.
77 years after he returns to Mordor.
1,019 years after the Nazgul have sufficient control over Mordor orcs to presumably form an army of them to besiege Minis Ithil.
1,039 years after the Witch-king comes to Mordor and gathers the nazgul, presumably bossing around the Mordor orcs.
1,719 years after orcs start multiplying again, presumably under Sauron's influence.
About 1,969 years after Sauron forms a new body and beings controlling evil creatures like orcs, ending about a millennium of orcish freedom from higher powers.
3,140 years after Sauron returns from Numenor and possibly ends a period of orcish freedom in Mordor.
And about 5,960 years since Sauron becomes active in Middle-earth again and presumably ends about 500 years of orcish independence of higher powers.
I think that it is a little presumptuous to assume that one knows which era Shagrat and Gorbag are referring to as the good old days without big bosses over the orcs. It is theoretically possible that they might be referring to the three ages when Morgoth was imprisoned in Valinor during the Elder Days.