O pyinstaller gera executáveis para windows, se executado no windows. Ao rodar o pyinstaller no linux, ele vai gerar um executável pra linux.

Uma forma de contornar isso é usar o wine. Crie um novo prefixo e instale o python, as libs que você quer e o pyinstaller, assim você pode gerar executáveis no linux e usar no windows.

Lembrando que o que o pyinstaller faz é colocar o python e todas as libs dentro do exe, então se o seu cliente não quer instalar o python, é pior pra ele pois cada .exe vai ter o python dentro.