Based off Isaac Asimov's Robot City series of books (which are actually written by other writers, not him) Robot City, the game, is a first person adventure with some similarities to Myst.
It isn't awesome or anything like that, but I have fond memories of playing the heck out of it. My father bought it when he bought our first PC back in 96 together with The Dig. Time Commando also came with my sound board at the time.
Anyway, I don't actually have problems making the game run on modern systems, but there's an awful catch: since it used 256 colors only, a color configuration not supported by modern systems anymore, whenever I play it, there's an annoying black trail following my mouse wherever I move it on screen.
Does anyone have tips to circumvent this particular problem? Maybe a similar problem with another game that you found a solution.

What do you mean 256 colours not supported, if you right click the shortcut, go to properties and then the compatibility tab you can set it to 256 colour compatibility mode.

Right click the game shortcut, click Properties, click the Compatibility tab and check "Run in 256 colors" . . . =)
Drat . . . Ninja'd again

I did a quick recheck here, running the game, just so that I wouldn't make any errors
Without that option the game won't even run. It gives me a message about the need of setting the display correctly and then exits. So, yes, I'm aware of that "run in 256 colors" thing.
See the attached picture for reference on what's the problem like.
Though, I am running the game in a Win XP virtual machine in my Vista machine. (So that I can run it into a window). But I'm not sure that would be the problem.

Try running it at 256 colors with 640 x480 resolution (on the compatibility tab) I believe that was what the game required. (might try win 98 compatibility also)

I seem to recall solving similar issues (cursor trail issues) on a couple of older adventure games by disabling DirectDraw, although not with the game in question (which sadly i haven't played yet), and not on a Virtual OS.
Can't confirm any of it though, as i have no idea which were the games in question.

The image you attached was especially clear for 640*480 and also had a band across the top. Hence my suggestion to run at 640*480 but the band makes me wonder if you might be running with some stretch and at a higher res as well.

The game will only run with 256 colors, 640*480 and visual themes disabled marked in the properties menu. It will run with both Win 95 compatibility (it's a win 95 game actually) and no compatibility OS config, Win 98 fails.
Disabling DirectDraw bears no effect on the problem. There are no DLLs in the game directory (only two exes and a dat file, besides eventual save games), so there's no change DLL option to solve the problem.
Oh, and the image I posted has the borders widely cut. It actually runs on a tiny screen (of that size precisely ) inside a large black area.
The only thing I haven't tried was to install an older OS since the Win98 copy I got in my college years ago fails to boot the virtual machine (actually any machine, somehow it's not a boot disk) so that I can install it. I'll try to track some copy down to see if I can get the game to work properly. I'm not in a hurry and I have even played through the game before tolerating the problem. But I though about asking you guys since you could come up with a solution that I could use in a future play through.
Thanks for all the effort!

This is a long shot, but have you tried throwing Linux on a VM and running the game with Wine? I've had some excellent results running older games like that in the past, much better than using the compatibility options in Windows.

did you try to set your whole system to 640 and 256 colors?
and maybe install win95 on your virtual machine?

I won't go as far as trying Linux + Wine, because I'm a zero with Linux. Never tried, hopefully never will.
Next step will be getting some Win 95 or 98 to try. It won't be so soon, since I have yet to find a copy (I own the keys though), but I'll update this topic with the results when I get there.

I doubt seriously that it will have any effect but . . . did you try setting the affinity (assuming you have a dual core)?
If you have an AMD Dual Core, I would try the AMD Dual Core Optimizer
If you have Intel you can either set it manually or use RunFirst.
Sorry I don't have any other suggestions . . . =)

"Rise from your grave!"

Just adding a definitive answer to this ancient thread.

I've met a youtube user who managed to play this game without problems (as his videos of it show) using Win 3.1 emulated in DOSBox.

I might try in the future, but I don't have any copy of Win 3.1 as of now.

EDIT: Marked Arkose's suggestion as solution since it is indeed a viable solution. :)

I can now officially confirm that the combination DosBox + Win 3.11 will allow the game to run properly. Thanks for the help everybody! :D