Set your resolution the what you want it at.
Add the line in your .ini file (civlizationiii.ini for VC3, ptw.ini for PTW, and conquests.ini for conquests) KeepRes=1. This may also affect your refresh rate, so find that and put in the line Refresh=XX, where XX is the refresh rate of your monitor.
I wouldn't use Video Mode, but it wouldn't hurt. It is useful if you want to play 'windowed'.