You'll find NX to be much, much better than VNC and RDP. A remote X desktop over NX will feel like a local connection. BTW, there will be increased overhead on the server side if you go the NX route, but that's nothing more RAM/CPU won't fix.
Mmmm, I've just setup NX and it seems very good. Takes a long time to start (60 seconds), maybe I haven't got it right yet?