Со своим товарищем пытаюсь поиграть в Heroes 3, но не могу установить соединение с его компьютером (или установить с ним Virtual private network? Я в терминах не силён). Компьютер товарища вне моей локальной сети.

Все программы, которые мы использовали, с моей стороны посылают подобные жалобы:

Symmetric NAT Router

Your internet connection is behind symmetric NAT router that will prevent you from playing peer-to-peer games.

Мой роутер мешает установить соединение? Как это можно исправить?

Вам нужно сделать проброс портов на роутере. Товарищу тоже, если у него также стоит роутер. Порты нужны такие (взято отсюда
http://heroescommunity.com/viewthread.p ... &TID=12141
из первого поста).
2300 to 2400 TCP & UDP (trigger port = 6073), 28800 to 29100 TCP & UDP (trigger port = 6667) and 47624 TCP and UDP
Первые два правила делаются в Application rules, последнее в Virtual server. Пробуйте.

Если это не поможет, остается только вынести компьютер в DMZ (хотя бы на время игры).

Кроме того, вы и ваш товарищ должны иметь нормальные белые IP, чтобы вы могли с ним играть в сетевую игру.