I've honestly had terrible success with VNC servers on Linux lately. In response, I've switched to often just using X-forwarding to run stuff remotely..
To try it, from another Linux machine, you can quickly (usually) get going by adding "-X" when sshing in:
$ ssh -X me@myserverbox
Once you've logged in remotely, you can run apps over the network just by calling them up:
$ xclock
If everything's well, you'll see xclock appear locally, but it'll be running from the machine you sshed in to.
You can actually run entire window manager sessions over this.. But it's a bit of effort and you definitely want a really nice network for it.
You CAN also run X servers on Windows, so you can Xhost apps over in to windows - and to do it in OSX, you have to install X11, run it and then ssh in from a terminal running on X11.
Hope that helps ya a bit.
Edited: To correct terminology error