All recent versions of Red Hat and Mandrake include packages for VNC servers and clients. In my experience the "tight" encoding works best for most internet links, while hextile is great for LAN connections. I personally am not positive about RealVNC and TridiavVNC, and the VNC version at AT&T is the ancient oldest version, don't use it.
When logging into the VNC server running on Linux from a Windows client, I use the TightVNC client from here: http://www.tightvnc.com/ K12LTSP distribution has an easy RPM of ltsp configs that allows on-demand VNC connections via xinetd. When you make a VNC connection, it opens a new XDM (or KDM or GDM) login screen just like your normal login screen in init 5. Their ltsp-configs RPM works on pretty much any version of Red Hat, and probably Mandrake too, if you have vnc-server package installed.
