Reinstall your video drivers. Also make sure that in 'Display Properties', your hardware acceleration level is set to 'Full'. Confirm that all DirectX / 3D features are enabled in 'dxdiag' as well. Advice: Make sure you have at least 32+MB of VRAM.
Besides, have you tried removing the gta_vc.set file located in the Vice City User Files folder? Have you tried re-installing the game? Do you have any mods? Where have you got the game from?
If nothing works, try putting one of the resolutions from this
post. Put the file in your Vice City User File directory (should be under my documents) and rename it to gta_vc.set and start up the game.
Did the game ever work before? Is 640x480 a supported resolution? Go to Display Properties -- Settings and find out what resolutions are supported. Did you also try to run the game in Windows 98 compatibility mode?