The first couple of things that come to mind are in the design of the network and workstation.
1. Limited accounts for the users, no administrator level for the staff this prevents many of the bad things from being installed. You may encounter resistance for 'restricting' the user's ability to do their job, but it will pay dividends in cleaner machines and in license compliance.
2. Perimeter anti-virus protection. Anti virus scanning on all email and Internet transfers (web, FTP etc.) at the gateway level keeps the bad stuff from ever reaching the desktop.
3. Look for the small footprint anti virus / security package for your desktops AVG - NOD32 - Kaspersky offer NPO discounts and have small footprint packages that can run on older hardware. Plan the licensing term of the software to match the service life of the PC. If the PCs will be in production for 5 years see if you can get a 5 year license on the AV software. If you are using off lease 2 or 3 year old machines, then a 3 year term on the software would be fine. That way the relicense fee can be bundled with the replacement hardware costs.
4. If it is a large network consider firewalling segments of the network allowing only necessary traffic between PC segments. Again like the perimeter protection, if a machine is going to be infected, limit the number of machines that the infection can impact.
5. Build the PCs on an image, allowing the PC to be rebuilt quickly in the event of an malware infection. Establish a design that all user data is stored on the server, and use as common of a PC software configuration as possible. Rather than trying to clean a machine, wipe the hard drive and reload the machine from the image library.
6. User skill and training, if you figure out the solution to this one let me know.
Dave