So here is how it works:
When I launch Pharaoh from Galaxy, nothing happens. When I go to task manager there's pharaoh.exe process. I close it. Then I click "play" in galaxy again. Now it runs. It works like that each time.

However, after I do the above, rundll32 process starts to occupy all the cpu that's left from other programs, so the cpu sits at 100%. Then it takes a breather for 2 seconds. Then it's 100% again. And so on.

EDIT: it's actually rundll32.exe*32 that consumes CPU which appears after I try to run Pharaoh the first time, there's the normal rundll32 as well that consumes ~0 CPU. It seems the *32 version has to run before Pharaoh, that's why running Pharaoh the second time works. If I kill rundll32.exe*32 and try to run Pharaoh the game doesn't start again but rundll32.exe*32 reappears.

I haven't noticed much performance drop to be honest yet. But I hear my PC working top speed. It's probably unhealthy.

Anybody know how to fix this?

" .. rundll32.exe C:\Windows\system32\gameux.dll,GameUXShim .. "
As it turned out, this is the functionality of "Windows Game Explorer".
It looks like MicroSoft collects statistics.
My Steam version of the game is trying to connect to 40.113.76.66:443
No one answers him there and he hangs endlessly in eternal expectation.
The problem is solved by everyone in their own way.
Someone radically removes gameux.dll from the system.
But there is a more civilized way through the creation and launch (from the Admin)
GameUX_OFF.reg

Windows Registry Editor Version 5.00
[HKEY_CLASSES_ROOT\Local Settings\Software\Microsoft\Windows\GameUX\ServiceLocation]
"Games"=""

It's funny that the "Compatibility Win95/98" mode completely removes the problem.