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:
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