Use NX. VNC sucks.
I love Remote Desktop for connecting to Windows machines remotely. I worked from home many times while at Kodak and if it weren't for Remote Desktop, it would have been impossible to enjoy a full-screen connection to my work desktop while at home. I didn't think there was anything for Linux besides VNC until now (I had used remote X a long time ago though, to connect to the Solaris machines at UBC). Then I discovered NoMachine NX (NoMachine is the company's name and NX is the product name). I downloaded the Free Edition for Linux and then grabbed the Windows Client (which apparently is also free?). It's ridiculously fast, as fast as Remote Desktop. Google is also working on neatx an open-source NX server implementation and there is the freenx project, a GPL-licensed implementation of the server and client components. If you are trying to connect to a Linux desktop remotely, don't even think about using any of the VNC derivatives. Use NX.