But there is still the question of why it took 20 years to build the Death Star in ANH, but less than 4 for the Death Star in ROTJ. Design issues maybe? The real answer is yet another problem with the prequels, but oh well.
It might not have taken 20 years to build the DSI. After reviewing the captured Separatist battlestation/DS-prototype/whatever, Palpatine might have decided he didn't want a Death Star. The DS was a weapon of political terror, intended to make a bold statement of Palpatine's supremacy over all Imperial member systems. But the immediate post-RotS era wasn't the right time for that. He still had to deal with his enemies in the Imperial Senate, reintegrate the Separatist systems, reconstruct the worlds devastated by the Clone Wars, rebuild and Imperialize the military, hunt down the surviving Jedi, and cement his reputation as a populist, "peace and security" ruler. Starting a superweapon at this point could tip his hand to his many surviving enemies.
Things had changed by the time of ANH. The Imperial Senate was on the way out, the Imperial military and navy were at the height of their prowess, and the Palpatinists ran the government and armed forces. Tarkin, who was obviously involved in the inspection of the Separatist battlestation/DS-prototype/whatever, had risen to the rank of Grand Moff and regional governor -- evidently a political/military executive directly below the Emperor. The Emperor's opposition had moved from the Senate hall on Coruscant to Alderaan and the Outer Rim. The conditions now made a Death Star program not just possible, but likely.
Most of the time used in the construction of the DSI probably went into setting up the supply pipelines, construction methods, and related technical expertise. Assuming that machinery survived the DSI's destruction, it could have been immediately reactivated to build the DSII. Setting up the industrial and bureaucratic machinery to build a Death Star would take a long time, but once it's up to speed, it might be harder to shut it down than to just start designing and building another.