I have been using Mac for quite a while, but did not have much time to explore many of its features. Today, I managed to find how to do easy VNC to my linux box using Screen Share application, a hidden treasure.
First, follow the instructions here to set up the Screen Share application. Somehow I could get the advanced toolbar working.
Second, you need to set up the VNC server on your linux box. In my case, Redhat Enterprise comes with VNC server installed already. All I need is to configure it properly. Follow this nicely written tutorial to start your VNC server. There are two ways in this tutorial: use the build-in remote desktop setup, or the DIY configuration. I chose the 2nd option since it is much flexible and the first one did not really worked for me.
Third, connect to your VNC server. In my case, I just typed in hostname:5091 and clicked connect in Screen Sharing, then it starts working, really cool!
I think you should be able to do the same with a Windows machine running VNC server, but I did not try that.