Why is the story of the spies repeated in Devarim (Deuteronomy)?
And, in addition, why is it different the second time?

In general, much of Devarim is a repetition of what was already taught. In fact, the Sages call it “Mishne Torah”, or “Review of the Torah.” One explanation of this, given by Rav Samson Rafael Hirsch, is that as Devarim is taught by Moshe just prior to Bnei Yisrael’s (the Jew’s) crossing over into Israel and embarking on there own, it contains those teachings most relevant to their new life in Israel and keeping a strong faith and avoiding the snares and temptations of their idolatrous neighbors. In many instances, the repeated portion elucidates and clarifies situations that might have been unclear the first time around. Certainly, in regards to the spies, if not for the repetition which clearly shows that the whole episode was initiated by the nation, it would have been difficult to understand why Moshe sent them in the first place.