There is no documentary evidence for this legend. It was most likely invented by the members of the Free Economical Society - historical sources prior to establishment of this society in 1765 make no connection between potatoes and Peter's persona. First actual historical accounts of potatoes in Russia are after Peter the Great's death - there are documented instances of potatoes being served at St.Petersburg's tables as early as during Anna Ioannovna rule (1730-1740), which coincides both with influx in foreign immigrants in Russia and with spread of potato cultivation in Europe.
Thus, the more realistic story would be that potatoes were brought by European immigrants and, for a long time, potato consumption was limited to those immigrants and the only people who interacted with them on a daily basis - the aristocracy.
So while it is doubtful that Peter the Great did introduce potatoes to Russia himself, it's his reforms that enabled the plant to spread to Russia.
Edit: this article (Russian language) notes that during Peter's times potatoe were unknown in most countries tzar visited in his travels, but Rissia did have a limited trade with England via the White Sea, and that in 1740s one of Russian potato popularizers Jacob Sievers wrote, that northern peasants grew a lot of potatoes, while in south the vegetable was treated with distrust. So potatoes might've come by the northern route.