So, I'm receiving an error message about no package exist for vcrun2015.

Sorry, my fault. First, I tried installing through Play On Linux. Didn't found vcrun2015 with winecfg, so I opened a terminal and wrote "winetricks vcrun2015". The output returned an error message: "Unknown arg vcrun2015".

Where do I get that vcrun2015? Maybe I need to register another PPA? I always installed through POL, so sorry if this is a noob question.

Thanks again Gydion.
Reading through i386-wine-devel make files, I think you're right about the building process. There was no doubt about what wine-devel needs to pull in order to be built.

I'll look more on that.
I'm not sure and since it's my main system, the last thing I'd like is to turn it unstable.

@JudasIscariot
I'll try to update Winetricks.
This is the output:
20140817 - sha1sum: b6ad9287523453a33e443ef2f4bd77f2f7f49e21

Unfortunately PoL doesn't support vcrun2015. It also won't install on any Wine prefix created by PoL if you use winetricks, you'll just get errors.

You need to use a clean Wine prefix (one that isn't created by PoL) and grab a new version of winetricks if you need vcrun2015.

Thanks Judas, I didn't know about the self-updater.

some more hacking around on Interstate 76.
The attached patch limits the fps to 30. That prevents any gamebreaking "I can't make that jump" cases (or the AI not making a jump). At least as far as I have played.
The physics still sometimes feels a little bit odd and the AI acts retarded at times, but I'm not sure if this is buggy behavior or simply a game from the 90s ;)
The patch also disable the funky cpu speed measurement, so no need to run it under win98.

to apply the patch:
download the attached file, save as 30fps.patch
then in the game directory:

~/games/interstate $ md5sum i76.exe
9a232dcc2c164648cff20c414c1f9698 i76.exe
~/games/interstate $ cp i76.exe i76_fix.exe
~/games/interstate $ xxd -r 30fps.patch i76_fix.exe
~/games/interstate $ md5sum i76_fix.exe
a6093422be1a941f48731bbd0da56f3a i76_fix.exe

then launch the game with: wine i76_fix.exe

Game: Space Rangers: Quest
de7c42f7a0e44abcb449745b02ccce83 setup_space_rangers_quest_2.0.0.3.exe
WineHQ AppDB link: none
CodeWeavers link: none

Kernel: 4.4.0-34-generic x86_64 (64 bit)
Desktop: MATE 1.14.1 Distro: Ubuntu 16.04.1 xenial
Graphics Card: NVIDIA GT215 [GeForce GT 240]
GLX Renderer: GeForce GT 240/PCIe/SSE2
GLX Version: 3.3.0 NVIDIA 304.131

Wine version(s) tested: Wine 1.9.18 via PlayOnLinux

Install notes: installs fine,
If using PlayOnLinux, run the game from/create a shortcut for SRQuest.exe"
How well does it run: runs great, finished the first mission without a problem.

Game: Gothic
Installer MD5: ff644047f11bb40ef08b45f519bc5eda setup_gothic_2.1.0.7.exe
WineHQ AppDB link: https://appdb.winehq.org/objectManager.php?sClass=application&iId=2153
CodeWeavers link: https://www.codeweavers.com/compatibility/crossover/gothic

Distro: Linux Mint 18 Cinnamon 64-bit
Kernel version: 4.4.0-36
Graphics card: Nvidia GeForce GTX 750Ti
Graphics driver & version: Proprietary 370.28
Wine version(s) tested: Wine Staging 1.9.18 via PlayOnLinux, CrossOver 15.2.0

Install notes: Requires directmusic (install "Direct Music" in CrossOver)
If using PlayOnLinux, run the game from/create a shortcut for "GOTHIC.EXE"
How well does it run: Almost perfect
Details: I have only played for a short while, but encountered no major issues & it seems to run almost perfectly. The game had a title bar initially despite running full screen but it went away after changing to a higher resolution and hasn't returned. Tested with virtual desktop enabled. Do not use CSMT as it'll cause the game to freeze on exit.

Open source engine reimplementation "REGoth":
There's still a lot of work needed but it's worth keeping an eye on: https://github.com/degenerated1123/REGoth

Any word on the latest Army Men trilogy? After a long and unsuccessful battle to get the last game I tried working (Interstate '82) I'm a little hesitant to buy this without any feedback from my fellow WINE gurus.

I've only tried Army Men (1) (which I dl illegally since it's not for sale here, but do own it on CD) and it will run, tried bootcamp and the grenade launcher part can't be completed, as the grenades flies of randomly, and there are times that it's hard to make out if your army man.