Russian imperfective and perfective verbs, in what is technically the imperative, convey different moods: сядьте and выйдите are imperatives ("do as you're told"), садитесь and выходите are optatives ("do if you feel like that"). This is close to English "go" vs "you should be going."
The same holds for interrogative dative constructs: мне выйти? means "do you want me to get off?" and мне выходить means "shall I be getting off?"
If you ask a stranger где мне выйти?, it would be somewhat rude for them to answer this question as asked and it's somewhat rude for you to force them to answer this question.
That's why you use the imperfective construct when asking the question.
If they were to answer you in the imperative, they would have probably used the imperfective in their answer too: Выходите на Площади Восстания. This would be a perfectly valid and polite answer, something you're likely to actually hear in the St. Petersburg metro.
But they are using an indirect phrase, and this modality rule does not work (or, rather, is much weaker) in this case. So they're using the perfective, as лучше всего вам выходить would mean something you would do every day, not just once.
The same way, you could have used the indirect phrase in your question: где мне лучше выйти and this would be ok too.
Also note that all above are very fine shades of politeness, so you can probably hear all combinations of perfective and imperfective in real speech.
It's very similar to the difference between "you should go" vs. "you better go" vs. "you should be going" vs. "you better be going" in English.