My god but VNC is slow from a Mac running leopard (10.5.6). Even running from the same network switch it’s like molasses. But from across an internet connection it’s nearly unusable. Not for anything fancy either, just plain old web surfing or following the mouse cursor! My goal is to be able to assist the in-laws with using the Mac we gave them for Christmas. But it’s too slow to even be useful.
Vine Server gives you more options than the native VNC server, like 8-bit colour mode, which is perfectly adequate for most remote operations. Vine also supports several graphical compression protocols, including TightVNC. I find Vine works quite well to control my home computer from work over my ADSL line, and that’s over via a SSH pipe as well. It’s free. Try it.