I ask this because at the end of the movie, you see Luke on Tatooine, Leia with Bail Organa, and then a decent portion of the Death Star already done as Palpatine & Vader look on. So it seems the station was already under construction during the Republic. Or was there just some random time gap between these scenes?
Here is the scene in question:
The Death Star was constructed during the Clone Wars. Wookieepedia has more information.
As the war raged on, the Ultimate Weapon saw construction over Geonosis. By the time the three-year conflict came to an end, workers had partially completed its framework. As the war ended, Darth Sidious got rid of his Confederacy puppets, including his own apprentice, and proclaimed the birth of a new, authoritarian Galactic Empire, anointing himself Emperor. The Ultimate Weapon project was immediately appropriated by the nascent Empire.
So there you have it- it was being constructed for up to three years. Remember that at the end of Episode 2 the Separatists had the plans. They had the resources of many star systems behind them, as well as the personal wealth of two influential Sith.
EDIT: I just saw something in another answer that can serve here as confirmation; the commentary for Episode 2 has Lucas say the following:
...I came up with the idea of adding a little schematic of the Death Star in here, because the Geonosians build robots and build things, they're sort of construction workers. They would probably be the ones contracted to build the Death Star, and they were the ones that Jay and Silent Bob worry got killed on the Death Star, but they are after all a bunch of large termites.
The canon novel Tarkin confirms that the Death Star was under construction before the end of the Clone Wars (which coincided with the end of Revenge of the Sith):
...getting to the truth of the [Death Star]’s origin was nearly impossible. Everyone from celebrated ship designers to gifted engineers wanted to take credit for the superweapon. Tarkin himself had discussed the need for such a weapon with the Emperor long before the end of the Clone Wars. But no one outside the Emperor knew the full history of the moonlet-sized project. Some claimed that it had begun as a Separatist weapon designed by Geonosian Archduke Poggle the Lesser’s hive colony for Count Dooku and the Confederacy of Independent Systems. But if that was the case, the plans had to have somehow fallen into Republic hands before the Clone Wars ended, because the weapon’s spherical shell and laser-focusing dish were already in the works by the time Tarkin first set eyes on it following his promotion to the rank of Moff—escorted to Geonosis in utmost secrecy by the Emperor himself.
Tarkin, p. 27
The scene mentioned in the question is evidently the event in which Tarkin first saw the Death Star at Geonosis. Tarkin evidently deduced that the Death Star plans had been acquired and construction had been started before the Clone Wars ended because the shell and laser-focusing dish were already being built.
The novelization of Revenge of the Sith also describes a bunch of events including the Death Star construction in the present tense in the ending, suggesting they all happen at about the same time, followed by a "then" showing Obi Wan riding off into the sunset:
The long night has begun.
Huge solemn crowds line Palace Plaza in Theed, the capital of Naboo, as six beautiful white gualaars draw a flower-draped open casket bearing the remains of a beloved Senator through the Triumphal Arch, her fingers finally and forever clasping a snippet of japor, one that had been carved long ago by the hand of a nine-year-old boy from an obscure desert planet in the far Outer Rim ...
On the jungle planet of Dagobah, a Jedi Master inspects the unfamiliar swamp of his exile ...
From the bridge of a Star Destroyer, two Sith Lords stand with a sector governor named Tarkin, and survey the growing skeleton of a spherical battle station the size of a moon ...
But even in the deepest night, there are some who dream of dawn.
On Alderaan, the Prince Consort delivers a baby girl into the loving arms of his Queen.
And on Tatooine, a Jedi Master brings an infant boy to the homestead of Owen and Beru Lars—
Then he rides his eopie off into the Jundland Wastes, towards the setting suns.
Note however that according to current Disney canon rules, novelizations prior to The Force Awakens have no canon value beyond what was already established in the movies. But at least this probably suggests it was Lucas' intention at the time that the scene took place around the same time as the scene of Obi-Wan dropping Luke off. Also, Pablo Hidalgo, one of the people in charge of current Disney canon, seems to think think the scene took place around the same time as the rest of the end scenes, since in one of the responses to this tweet someone said "I always felt like this scene took place a few years after the suit went on" and Hidalgo responded "If it was the last scene, maybe. But it's intercut with other more immediate stuff." And in the tweets here and here he suggested maybe it was a Big-Dig-like project that overshot its expected completion date by quite a lot.
Legends-based answer: One of the first missions in Battlefront II takes place on Mygeeto during the Clone Wars, where the objective is to retrieve a crystal that the Chancellor needs for a superlaser, which is heavily implied to be for the Death Star. Later, this was identified as being part of Project Hammertong, which had been established in other EU works as a code name for the Death Star project. So at the very least, the superlaser section of it was being constructed during the war.
Canon answer: There's no indication that the scene during the montage at the end of the film is out of order, and there are in fact a few details that seem placed to establish that not much time has passed (young Tarkin, V-wings instead of TIE fighters), so presumably this is soon after the previous scenes.
According to the film's junior novelisation, Sidious and Vader appear to have visited the Death Star within a few days of Padmé's funeral on Naboo. The book describes it as "shortly after".
Obi-Wan and Yoda watched the funeral from Bail Organa’s starcruiser. It was as close as they dared come. The Emperor’s attention would surely be fixed on the funeral, and they would not take the risk of being found.
Shortly after, the Emperor took his new apprentice off to a remote area of the galaxy where construction of a new superweapon was just beginning — a gigantic space station with the power to destroy whole planets with a single laser blast.
This obviously means that the DS1 was under construction well before the events of Episode III took place.
I doubt it was under construction during the Clone Wars... Phoenix Squadron goes to Geonosis about 2 BBY and there was no death star.
