After a bit of searching (and, more importantly, asking my sysadmin friends...), I decided to give Duplicity a whirl. It's a Python based program with librsync at its heart, and supports a number of transports. Most importantly, it compresses the files, but in a manner that doesn't break their seekability in the way that a .tar.gz suffers. It also does incremental updates without breaking a sweat, so it looked perfect.
I fairly quickly got it set up on our backup linux server, and once I discovered Duplicity didn't support "pulling" backups, on the other Linux box also. Setting it up to do a weekly full backup and daily updates of important files was a breeze (with the help of a short perl script). That only left files from the Windows box, which are available under a samba mount.
At this point, things stopped going smoothly, as Duplicity barfs about half way through either mount, with a file not found somewhere very deep in its guts. This is a bit of a pity, as no-one has seen it before, and looked like a show stopper.
My mailing list post searching did throw up the fact that Duplicity worked quite well under CygWin on Windows boxes, so I thought I'd give that a try. I grabbed the installer, and was pleasantly surprised by how easy it all was. In no time at all, I had a Unix like environment, and ssh working.
Took a little bit more work to get sshd going, as the manuals lacked anything CygWin specific (and something was definately needed). A quick bit of googling pointed me to this, and I was away.
Librsync and Duplicity built and installed without too much trouble (once I'd altered the library search path), and with that my backups were good to roll.
As a bonus, I now also have a sensible Unix environment on the main Windows box at work, so it's a win/win outcome :-) If you do have to deal with Windows machines, and don't have CygWin on them, I'd advise that you go take a look at it now. Makes your life soooo much easier....
Update Someone has asked me how I "altered the library search path", and I currently have no idea. All I know is that I have librsync in /lib/ /usr/lib/ and /usr/local/lib/ .... I'll have to see if the answer comes to me