Edit the Prefs.ini file to reflect your desktop resolution.
The lines you need to look for are:
[Video]
DisplayWidth=(your display width)
DisplayHeight=(your display height)
Note that there is a separate Prefs.ini for each version of the game, each in their respective folder (which is found in My Documents\My Games\GalCiv2, etc)