Specify the chipset first, then features. Get the vendor to suggest several and then google them by name and manufacturer. Try to get boards that are about 6+ months old. Look through the HCL on LQ
The manufacturer matters less than the chipset where Linux is concerned as there are no backroom deals with the OS maintainer. Strongly suggest intel everything.
I did this myself very recently and selected constraints on chipset (intel), processor (P4 or core2), and price (NZ$500 but prepared to go a bit over) ... beyond that, it needed to be able to take existing RAM, IDE drives and AGP card.
Ended up with E4300 core2 duo and asus p5pe-vm ... 100% compatible, no install issues, and didn't even need that agp card as onboard 3D is sufficient. So, I have no (zero, zip, null, nada) proprietary thingies at all.