Executando less como
LC_ALL=ru_RU.CP1251 less file
contanto que ru_RU.CP1251 locale exista em seu sistema (veja se LC_ALL=ru_RU.CP1251 locale charmap retorna CP1252) diz less que você está nessa localidade, o que significa que file está codificado nesse conjunto de caracteres e que o terminal usa esse conjunto de caracteres.
Se o emulador de terminal foi iniciado em uma localidade onde o conjunto de caracteres é UTF-8, ele esperará que os caracteres codificados em UTF-8 não saibam o que fazer com os caracteres codificados em CP1251 que less está jogando nele .
Você também precisaria iniciar o emulador de terminal naquele local ou usar luit para fazer a tradução (desde que o conjunto de caracteres do terminal seja UTF-8).
Ou você pode usar iconv para converter o arquivo no conjunto de caracteres do código do terminal:
iconv -f CP1251 < file | less