Okay, so the PC "logs in" to view what the Arduino has on its "screen." The Arduino definitely does not have enough RAM to actually have a regen video buffer. So the image has to be generated on the fly, whenever the PC's VNC client is requesting an update from the Arduino server's screen. Once the whole image has been generated, the Arduino could update smaller portions of the screen area, and the PC client would show those updates live.
I can see plenty of things this is useful for.
In fact, you might be able to stream the contents of one of those super-cheap video camera components on SparkFun. Or make a text/bitmap display that can summarize the status of a weather station. Or a microscopic command shell that lets you do live hardware I/O.
follower, VNC also supports sending keystrokes and mouse input from client to server. Have you played with that part of the loop yet? As for the "byte at a time" problem, I thought someone was already fixing that?
And which Ethernet shields/adapters are you using?