I run the game on two PCs (laptop and desktop) based on Mint 17.3 64 bits using wine-1.9.5 (devel).
If anyone is interested I could try it on Debian 8.3 64 bits too.

Create a clean 32 bits WINEPREFIX:
WINEARCH=win32 WINEPREFIX=~/.wine_sots winecfg

Download winetricks if you haven't got them already:
wget https://raw.githubusercontent.com/Winetricks/winetricks/master/src/winetricks

Install tthe following libraries using winetricks:
WINEPREFIX=~/.wine_sots sh winetricks d3dx9 vcrun2005 corefonts

Install the game:
WINEPREFIX=~/.wine_sots wine setup_sword_of_the_stars_2.0.0.3.exe

I've used the graphical installer and just ignored the error messages at the end.
The game is ready to run.

I haven't had the time to test it much, but it seems stable until now.