Какую конфигурацию прокси сервера выбрать?

2) не слишком принципиально - http прокси в режиме connect работает идентично socks прокси, различается формат запросов и механизмы авторизации. Кстати по поводу авторизации - придумайте, как отфильтровывать всех, кто будет использовать ваш прокси в личных целях, без расширения.
3,4) некоторые прокси на каждое подключение создают новый поток, это может сказаться на производительности. Выбирайте такой, чтоб и памяти потреблял немного (а на каждое соединение необходимо выделять буфер) и работал в несколько потоков (но не создавал поток на каждое новое соединение)

P.S. было дело, писал свой быстрый http прокси под видео стриминг. на таком количестве клиентов не тестировал, если интересно, напишите, попробуем...

если расматривать ксен или квм то без разницы, все равно их придется брать много , если смотреть на 10 000 юзеров онлайн и каждому хотя бы мегабит давать то это уже 10 серверов, а если по нормальному хотя бы 10 мегабит, то тут уже надо сотку серверов .

смотря для чего нынче http2

тот с которорым у вас больше опыта

зависит от нагрузки ,в целом все пишется в лог и всегда можно узнать что не так что то