Антон, на компьютерах пользователей вы можете использовать OEM-лицензию Windows, которая шла в комплекте с компьютером. Если же OEM-лицензии на компьютере нет, вы можете использовать Linux, как предлагает
Drno .
На серверной стороне вам надо установить (и платить за) только Remote Desktop Services SAL по количеству человек, которые будут подключаться к этому серверу. Т.к. ваш провайдер работает с Microsoft по схеме, которая называется, SPLA, то никаких других лицензий на подключение тут не надо (в отличие от корпоративного лицензирования).
Дополнительные лицензии могут понадобиться, если вы захотите использовать, например, Microsoft Office на этом сервере или другие продукты MS.