I set up VNC running on my RedHat 7.3 box on the local LAN by following the steps at:
http://www.frankhilliard.com/remotelinux.cfm
I can run vncviewer against this no problem (remember to choose display 1) from WIndows 2000. I have also accessed this box via an 8Mb pretty congested WAN link (NT4.0) and also via dial up (Win98 + 56k modem) and whilst it wasn't exactly zippy, it wasn't any slower than anything else, and much faster than pcAnywhere on NT.
Tip - Use TightVNC (
http://www.tightvnc.org) you'll see about a 30% performance increase over VNC. Over a LAN it's hardly noticeable but over dial up it flies in comparison. You might also want to consider tunnelling it over Zeebeedee (haven't used), Stunnel (have used, works fine) or using ZVNC (haven't used -
http://home.attbi.com/~davedyer/znc/zvnc.html)
Flibble