Then you need to try to find and delete the configuration file for that game. It should be somewhere in "C:\Users\YOURNAME\Documents\GTA Vice City User Files" or something like that. That directory should store game settings.
You can do one of two things.
Delete "gta_vc.set" file and start the game. Access the settings and change your resolution.
Try to open "gta_vc.set" with Notepad (double click the file and choose to open the file with Notepad) and search for "640" (press the ctrl and the f key on your keybo ard to do the search). After finding that number, you can change that to your resolution.
For example, it it might look like this (change 640 to 1366 , 480 to 768, and 16 to 32):
Res_Y = "640"
Res_X = "480"
Col_bit = "16"
You can also try running the game in compatibility mode.
Right click the shortcut, select properties.
Then click the compatibility tab.
Click the "Run this program in compatibility mode for:" square and select "Windows 98/Windows ME".
Also, double check that nothing else is selected in that compatibility tab. For example, the "Reduced color mode" or "Run in 640 x 480 screen resolution" should probably not be selected...