Solution 1:

OS X Leopard with its own ScreenSharing client, connecting to another OS X native screen sharing server, does some negotiation on colour depth, etc., so it's transferring less data.

(You can see this effect exaggerated if you connect to an OS X system from Windows using the RealVNC client over a higher latency connection. It will take a long time to build up the screen output.)

I couldn't find a way to make RealVNC request a lower colour depth so what I did, to work around this, was run a copy of VineServer on OS X with the '-maxdepth 8' option (and '-rfbport 5901' to run it as an alternate server), and connect to that when I connect long distance (which I always do through an SSH tunnel, before anyone states the obvious.)

Solution 2:

I've switched from UltraVNC (back) to RealVNC, primarily because UltraVNC was not handling my multi-monitor server right.

Solution 3:

I found switching to Vine Server rather than the default Apple one made a huge difference to performance.