Easily explained. The first Death Star is the original one, so you have a lot of time and resources focused on research and design that must be carried out by the engineers working on it. For example, the mechanical engineers may have designed the super-lazer by Episode III, but actually building one that operates correctly and efficiently, and then testing it, is very different and could take years in itself. By the time we get to the second Death Star, the R&D is cut way down because they already know how to build the working machine.
The second problem with the first Death Star is that the Emporer has to divert funds from other government sources without the Imperial Senate knowing. Considering the Death Star would require the complete mining of a small moon for its materials, it would not be an easy task to divert funds without someone in the government noticing. Obviously this could cause a lot of delays. During the construction of the second Death Star this problem does not exist. Palpantine could divert as much funding and resources into the Death Star as he desired since only the location of the project needed to be hidden from the government. In addition, although the second Death Star was larger than the first, I believe the RotJ book says it was only 60% complete in its structure.
Finally, we don't know when construction of the second Death Star was begun. It may have been immediatly after the Battle of Yavin IV, but the Emporer could have had plans for a second one before then. If we take the conservative approach and assume Palps began construction immediatley after Yavin IV, that gives the Empire 3.5-4 years (not 2) to have it built to the point where it is by the Battle of Endor.
