Appear in what soon will be Poland, around 960s. The warlord family of Piasts is just starting their campaign to unite Western SLavic tribes into one identity, the "people of the fields" AKA Polish (from pole - farmfield).
Find the Piasts, preferably the young and ambitious Prince Dagoberth Mieszko.
The Polish Kingdom is only now being established. The Piasts are going around the place, conquering new towns and keeps every day. The establish completely new rule, new taxes, new economy, etc. Creating administration, bureaucracy, coinage and law from scratch. They are also introducing Christianity (begrudgingly) and bringing in monks.
Show the Piasts the usefulness of the potato. They were exactly the kind of people who would have the charisma and conviction to just force the farmers to try a new crop, since they were already revolutionizing the place. They were also big showoffs, and loved to dazzle the Western dignitaries with their wealth and "worldliness" (When the German diplomats arrived for Boleslav's coronation, Boleslav brought camels from Arabia to impress them. "Exotic" potatoes could serve a similar purpose on the feast.)
Potatoes are hard to introduce, because Europeans distrust them. Early Poland was ruled by a ruthlessly dominant dynasty with a very progress-oriented attitude.
Besides, the area between the steppes of Ukraine on the East, and the German lowlands on the West is arguably the best in the world for growing potatoes. Medieval Polish Kingdom was smack-dab in the middle.
Third reason: if the potato revolution starts in Poland (possibly with a quick intro on the idea of crop rotation) you can have a second civilization center in the middle of the Europe, sufficiently away from Rome that they won't compete much, and sufficiently away from Vatican that they cannot meddle with progress too badly (but still could send monks back and forth to spread the Godly Tuber to the faithful).
Last reason, maybe minor but still; throughout the history, Poland always had cordial relations with Scotland, Ireland, Hungary and Bulgaria. All those places would also be ripe for Potato Revolution, while forming an economic counterpoint to the Saxon-dominated "imperial" Europe.