This version:

"Évához megyünk, Katihoz vagy Péterhez?"

has "Évához" in front of the verb. So, "Évához" is emphasized. The other people just by default inherit the same emphasis.
It could also be:
"Évához, Katihoz vagy Péterhez megyünk?"

The logic is clearer here, but they mean exactly the same thing.

Now, if you put the verb "Megyünk" in the front, then the focus is on the verb. "Are we going or are we not?"

It's isn't entirely wrong, but now you're asking if it's true that we're going to at least one of {Éva, Kati, Péter}. In other words, your translation is a yes-or-no question.

It should be Évához and Péterhez, but the word order is okay.

This sounds a lot better :-)