VNC is a good deal slower than RDP and ICA, and VNC is usually only used to connect the currently running desktop, while the Terminal Server creates a desktop for each user that remote connects. I don't think that a remote session will ever get anywhere near the performance of a Parallels session, but I'd say that it will always be faster than good old VNC.
They actually send bitmaps over the air and the clients use a local "bitmap cache". So, yes, the server does all the rendering.
Since you have Windows in Parallels:
Try downloading the Microsoft RDP Client for Mac from
http://www.microsoft.com/mac/downloads.mspx and connecting to your XP installation running in Parallels.
You'll have to enable Remote Desktop in XP, switch off the XP firewall (or allow the exception for RDP) and you probably also have to (re-)configure Parallels to use Bridget Networking and give the XP "machine" an own network address that is reachable from OS X.
But then you can already get your first impression what an RDP connection will look like on a local network. Just launch RDC for OS X and type in the IP address of the XP VM. It's basically the same technology as in Windows Server, the main difference is that XP is limited to one connection only and that you cannot use the "console" while a remote session is running -- meaning that you'll see the logon screen in Parallels while you are connected via RDC.
Since Windows Server 2003, remote sessions can be forced to "console mode", meaning that they are treated the same way as if you were typing on the server's own keyboard, with the same privileges. Before Win2003, this was not possible and imposed several restrictions on the remote users. However, I think there can still only be one console session running, and I do not know if the Mac RDC client supports console mode at all. On Windows, you have to launch the RDC client with an additional parameter to enable console mode.
Another important thing when you are installing software on a Terminal Software: Make sure you always do it through Control Panel/Add or Remove programs --OR-- manually switch the server to "Installation Mode" via typing in a command on the command prompt. (Can't remember what it was, but try HELP. ;-) Since Win 2003 things became quite stable and robust, but forgetting this in an older version of Windows Server your corrupt the entire server (no, I am NOT kidding -- I've killed a few NT 4 Terminal Servers in my time by not entering INSTALL MODE).
Ok, it's early in the morning again - bedtime for little Winni.
Good luck! :)