Regarding a small proxy appliance, my thanks to those who responded either on this list or by direct email.
We are going to get one of the little Acer AspireRevo 3610 boxes and give it a try. It's small, quiet, runs cool, and has more than enough resources to handle our CentOS proxy application. It's a shame that we have to trash the Windows-7 install (a waste of money) but that's life.
The only unanswered question is with regard to an external USB wired network adapter, so we'll have to go by the data on the various manufacturers' web sites about Linux support. Has anyone tried the Belkin USB2/Gbit, the D-Link DUB-E100 or the Linksys USB300M devices? Which adapter chips to they use (in other words, which driver)?