When exactly was the Destiny ship launched? And how does that compare to other important events in the Stargate franchise, such as Atlantis leaving Earth?
Depends on what source you look at
Stargate Universe: "Air, Part 1" — "Hundreds of thousands of years ago"
In the first episode of Stargate Universe, Dr. Nicholas Rush says the following:
"The design is clearly Ancient, in the truest sense of the word. Launched hundreds of thousands of years ago. Faster than light, yet not through hyperspace. Who knows how far it's traveled."
This would be after the war split between the Alterans and the Ori "millions of years ago" (Stargate: The Ark of Truth), as well as Atlantis' departure from Earth "several million years ago" (Stargate Atlantis "Rising, Part 1"), but before the Goa'uld began taking over hosts and ruling the Milky Way galaxy.
However, Atlantis has more advanced technology than Destiny, suggesting that Rush is severely underestimating the age of the ship since one would expect that Destiny would only use more primitive technology if it were older.
Stargate Universe: Back to Destiny #2 — "Approximately one million years ago"
Earth orbit. Approximately one million years ago…
This comic also establishes that Atlantis was "a competing project with the same mission". While the fact that it was a competing project may explain the technology difference between Destiny and Atlantis (given that the two efforts may not have been sharing technology), the timeframe of "one million years" does not match the pilot episode of Stargate Atlantis showing the city rising "several million years ago."
Joe Mallozi's blog — "About 60 million years ago"
Executive producer Joe Mallozi addressed a reader question on his blog.
Gabriele writes: “3. Destiny is older than Atlantis. In “The Lost City” we come to know that Atlantis is about 30 million years old. The gate aboard Destiny is older than the ones in the Milky Way. In “Frozen” we come to know that the gates in the Mily Way are about 50 million years old. Is the Destiny about 60 million years old?”
Answer: Damn that’s old. If Destiny is older than the Milky Way gates then yes.
Given that the Stargates aboard Destiny appear to be an older design than the Milky Way gate found in Antarctica (which was established to be 50 million years old), I think it is correct in saying that Destiny is older than the Milky Way gate network. Thus per Joe Malozzi's statement, Destiny was likely launched around 60 million years ago.
This would mean that Dr. Rush was orders of magnitude off in his estimate of the ship's age, but it is consistent with the statements about the age of Atlantis and the war with the Ori, which are implied to be more recent given the more advanced level of technology.
True enough. 60 million years ago was the launch of Destiny. In SGU, Eli was able to pull up a map of Destiny's journey so far. If you freeze the map for a closer look, based on her FTL drive speed, the distance traveled so far coincides with the 60 million years ago launch date.