Is it normal for VNC performance to be really slow? In our small network, windows remote desktop works seamlessly, but when using VNC to connect to some ubuntu machines I can barely work even on 640x480!
In my experience Windows Remote Desktop is usually faster than VNC but on the same network VNC shouldn't be running super slowly.
If your video card drivers are not up to date you could see some lag caused by that. You might also try turning off Differential Compression. You can do this by clicking Start and typing optionalfeatures.exe into the searchbox and press enter. Then just find it and untick it.
As Bob mentioned, part of this is also going to depend on which VNC you are using. Other than the two mentioned by him I have also used Crossloop which was only little slower than RDP. You might also notice an issue between Vista and XP machines.