Like I said, a very simple and obvious hint. Last night, I switched the background to a flat colour only, and the increase has been almost astronomical. I had all manner of fancy images used as desktop backgrounds on my Mac. The speed isn't too bad, but I've found a very simple (and once you know, completely obvious) way to increase the connection speed.

I use VNC on an XP box at work to connect to my Mac at home.