Frontier First Encounters is so good that I've uploaded the Windows version (thanks th4t1guy
for the pointer) to the zone.
Just extract the folder and run "FFewin26.exe". The game runs in a window and can be made full screen using "Ctrl+F12".
I have no idea what the min specs are for this DirectX version, but it runs like silk on my Duron 950. The DOS version ran perfect on my old 486 100 so I think most of you will be fine.
For more details and hints on how to play the game, visit the website I've linked above!