After installing disc one of Star Trek Starfleet Academy navigate to the install folder. On my system it was located here:
C:\Program Files\Interplay\Starfleet Academy\
Right click on the file:
Select the Compatibility tab
Select the following settings:
In “Compatibility mode” check “Run this program in compatibility mode for:” and select “Windows XP (Service Pack 3)” from the drop down menu.
In “Settings” check “Reduce color mode” and select “8-bit (256) color” from the drop down menu.
Also check the boxes next to “Run in 640 x 480 screen resolution” and “Run this program as an administrator”.
Enjoy the Star Trek goodness.