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.
EDIT:
Parece que agora você está usando o Python 3.7 no windows - Parece que tem um bug no pyinstaller nessa versão do python - tente usar o Python 3.6;