Александр

NAT.
Не ругайте меня. ;) лет 10 назад так бы сделал.
iptables вроде устаревает, аналоги есть. Принцип аналогичен.
Есть основной интерфейс eth0.
Есть интерфейс клиента vpn (на маршрутизаторе устанавливаем клиент vpn).
Перенаправляем нужный поток на интерфейс c vpn. И почти всё.
Там при запуске vpn клиента может перезаписываться маршрут. Если цель находиться в vpn сети там все просто (в настройках пишется строчка). А если сайт на просторе интернет, ставим внешний vpn сервер.

Частичное решение...
Поставь галочку "Разрешить другим пользователям ... Интернет" в свойствах адаптера.

3 года назад - Какой роутер (шлюз) купить?
18 лет назад - Гигабитные шлюзы VPN

И не будет проблем с большим количеством пользователей (тысячи, а то и миллионы)?

Только железки смогут выдержать ... можно конечно поставить Linux с OpenVPN, но мне кажется рискованно )))
В поисковиках - "vpn шлюз купить"

Как организовать авторизацию, на сертификатах или как-то иначе?

Для личного пользования я оставляю только сертификат, а всех заставляю пользоваться сертификат+пароль )))

Я бы ответил: никак.
1. На WIN2000 когда то делали подобные вещи, но в конце все равно перешли на ярлык ручного запуска.
Что бы запустить VPN нужно что бы сетевой адаптер прошел инициализацию и получил ip адрес. На vbs писали скрипты. gpedit.msc - Конфигурация компьютера - Конфигурация Windows - Сценарии. А дальше проблемы. Сеть не поднялась (DHCP тормозит или комп) запуск в ручную.
2. На маршрутизаторе разрешаешь только VPN трафик и к IP VPN серверу. Проблемы: Начиная где то с Windows7 не получая доступ в интернет пишет что то: "Подключение по локальной сети без доступа к интернет" и голову разбей - подключения не будет вообще.

1. Надо разделять приложения для настройки Клиента и приложения для настройки Сервера.
2. Надо разделять сами VPN - их там не много, но они разные.

Они все очень простые, устанавливаются буквально в одно нажатие.

Да. У меня сложнее. Надо установить TAP-интерфейс, OpenVPN и переписать в папку 3 файла. Это сарказм ))). Хотя вы правы, перед этим пришлось по мучатся - настраивать сервер VPN и тестировать.
3.

хотя я для телефона видел приложение, там был пробный период и 59 руб. в мес

Повторяюсь - переписать в папку 3 файла за 59 руб. )))
4.

А на телефоне скачал приложение, оформил подписку, от силы минут пять. Всё, готова. Ну почему так?

Повторяюсь - потому что сервер настроен , клиент установлен и нужно только файлы с настройками переписать. Вы соединяетесь к готовому VPN серверу.
5.

А для Linux я ещё ни одно не мог найти. Предлагаются какие-то профили конфигурации, которые у меня так и не получилось настроить, какие-то команды для терминала, которые тоже почему-то не работали

Проблема в установке и настройки сервера. Пример, NethServer, бесплатный, управляется через веб-интерфейс, но это сборка Операционной системы и там есть маленький пункт VPN. Что бы подключить клиента к VPN надо нажать 3-5 кнопок. И вам предложат сохранить сертификат по которому надо входить.
6. Хочу вернуться к 1 пункту.

Они все очень простые, устанавливаются буквально в одно нажатие

Это, скорее всего, готовые "сборки" (как бы их назвать?) под определенные сервера.
7.

мобильных телефонов iOS, android, даже для компьютера Windows

Уверяю тебя, это "срубание бабла", по тому, что VPN уже есть в этих операционных системах, кроме OpenVpn, VPN не надо устанавливать. Ты платишь только за запись в твое устройство от 1 до 3 файлов, об доступе к интернет пока не будем говорить.
Для Linux - нет приложений для клиентов. А зачем? Там нужно: Приложение такое же как на сервере и несколько файлов.

что делать с vpn fingerprint

MTU 1280 - подсказка что не так. Cтандартный MTU = 1500 (приблизительно, точно кажется 1492, но могу врать). К портам отношения не имеет.
Менять VPN Server ))), точнее тип VPN.

Где то уже были похожие вопросы...там были ссылки на статьи по типам VPN серверов.

Сам не делал но....
Разделяем задачу на 3 этапа.
1. VPN сервер. Клиент получает IP адрес с маской /32, те к каждому клиенту придется прописывать сеть из одного IP. Если нужно разделить VPN клиентов.
2. Ставим прокси, например Dante, можно попробовать через Docker, в котором также прописываем пользователей и пароли.
3. Весь трафик Клиента VPN перенаправляем (или как то перехватываем) на наш прокси через iptables. Что возможно не обязательно - в браузерах сразу можно прописать адрес сервера.

https://habr.com/post/216295/

Помню где то статья была с 7-мю пунктами

Возможно, на сайте используются устаревшие или ненадежные параметры безопасности протокола TLS. Если это будет повторяться, обратитесь к владельцу веб-сайта.

На всех браузерах? OPenVPN не причем )
Проверь антивирусы....
Эти "редиски" при включенной опции проверка сертификатов подсовывают свои сертификаты - зачем то ?!!!?
Открываем страницу в браузере. Перед адресом есть замочек. Пытаемся посмотреть сертификат сервера (на разных браузерах по разному). И иногда в сертификате написано что нет доверия поставщику сертификата. Используя поисковик ищем корневой сертификат AVAST, Kaspersky...(с ними были как то танцы с бубном). И добавляем их как доверенные центры сертификации.

ИЛИ ищем в настройках как отключить проверку SSL/TLS.