What distribution of Linux are you using? Most seem to come with a remote desktop client already. Open a terminal shell window, type "rdesktop xx.xx.xx.xx" with your Windows 2003's IP address and it'll come right up, just like Remote Desktop Connection does on WinXP machines. If you don't have the client program on your system, you can get it here: http://www.rdesktop.org.
Edit: It looks like you're trying to replace your Windows server with the Linux server (uh, is that right?) and are looking for a terminal server for it. VNC certainly is the best choice for that scenerio.