Get on Google for "multi seat x11". I read an article once where a desktop was used for 4 or 5 seats (keyboard/mouse/display). However at the time, one card was used per seat. Using dual head cards had problems. The article was a least 2 years old, so the status may be different.
Another option is to run thin clients. Then the keyboard, mouse and video traffic travel on the network. There are some thin clients that use very little power. These clients would load in the operating system from a server when they boot up.
I have read about potential problem. If you have non-postscript printers, they may cause an excessive load on the network while printing. I read of an example of a library using thin clients, running off a single server (on a 100MBS network).
Before you had powerful desktop computers, you would have X terminals connected to a central mainframe. This is what X11 was invented for.
A third choice is to have the system directories mounted on a central nfs directory. Doing this, the same program and library directories are mounted for each client. The individual home directories can also be mounted on a central NAS. The /tmp, /var/run directories could be mounted locally on a smaller drive. There is a document at the www.tldp.org
website called the "The Linux Filesystem Hierarchy Standard" which describes which directories can be mounted read-only and shared on the network. This means that in a heterogeneous environment, you could install or upgrade programs (as root) once, centrally instead of upgrading each computer.
The main difference between this and using thin clients is that with thin clients, the applications run on the server. Here the applications run on each computer but most of the filesystem is mounted centrally and shared. It is also possible to mount everything on a server and use thin clients. However here, the apps can run on the host.
The worst option, IMHO, is to use a Virtual Networking Computing server (Not to be confused with the term Virtual Network Connection). The entire session and the programs run on the server. So the server is loaded down running all of the apps, and the windows manager as well, which also causes more traffic because the entire screen is drawn at the server.
Linux (and Unix) use X11 which is network transparent. So it is possible to run an application on one computer but have it displayed on another display. The X11 terminal is the server, and the application is the client. Where an app runs isn't that important. I think the best solution is to run KDE or GNOME on a client and maybe run the apps on a server. You could have the filesystem mounted on a central fileserver(s) and the apps running on a separate server or servers. Each tuned for their particular task.
I hope I gave you some ideas, and haven't got too wrong or outdated. I didn't even cover virtualization, which is more like the VNC solution. This is used to virtualize servers (and/or clients) on fewer real servers but treat them as real entities. This allows you to be more efficient in purchasing equipment. A DNS server may be underutilized. Why have a real machine dedicated for the task (plus a backup).