Hello, FoP (Friends of the Penguin).
I tried the game under Xubuntu 8.10, Wine 1.1.16 on an EEE 900A.
The game will not start with the Europe1400.exe, I have to use the Europe1400_TL.exe.
The Game works and is playable, but has severe performance problems. I set all details, line of sight, ... to the lowest settings. It still maxes out the processor, and is extremely sluggish (maybe 7-10 frames per second in buildings), especially in town view (maybe 1-2 fps). This gets worse as the game prgresses and more buildings are erected.
It is still sort of playable (and quite addictive) if you are very determined (or bored). All gameplay mechanics (aside from known bugs that also occur on the windows version) seem to work as intended (played a bitas alchemist, blacksmith, money lender, & preacher).
A beefier machine might be capable to remedy that a little bit, or a better graphics chip - however, I do not have access to something else right now.
I also tried running the game from a ramdisk (It was installed to a SD-Card), however that did not help, so it is not I/O bound. Various Wine settings (Windows version, ...) did not have any effect. Setting the colour depth to 16 was futile, too.
Wine outputs some error messages about texture conversions, however as I have no clue about 3D programming/engines/... I am unable to make something of that.
As it is, I would advise against running the game under Linux or Wine, especially on low-end machines. If you have a faster processor, please try and let me know if that helps.
If you are interested in this type of game, rumour has it that Patrician 3 (also available from GOG) works significantly better. However I have not tried this myself.
And, if somebody finds a solution to the problems, please let me know. The game is really quite fascinating...
[edit]
Tried wine 1.1.17. No change. Game uninstalled until I have a dual-boot system again.

Pretty much any 3D is terrible on the eee900, whether it's native or Wine. My performance is great on my P4 3.0/Radeon 3850 on Wine, but it should be expected to play well on hardware that outclasses its requirements so much.

It is probably due to Wine's d3d8 not being able to use hardware rendering for fog, dropping instead to manual software rendering which makes the game very slow indeed. I determined this by setting different fog_plane value (from no fog at all, which counter-intuitively drops the game's framerate, to full fog, which completely covers the main game screen in blue, but maintains the game speed and framerate.)
I've tested on Debian wine 1.1.15-1; I've yet to try on the latest experimental Wine 1.1.22-1.