I’m also in the early stages of planning out a linux box. Because I’ve never built one, I’m aiming for easy and cheap to minimize the risk of screwing up and the cost if it does. I’m also thinking about using a P4 or Celeron because I’ve been told that those are easier to install than AMDs.
I’m thinking about the ASUS P4PE or P4S8X, both of which are somewhat older (=cheaper).
You may want to check out
http://www.motherboards.org/forums/ They have a section on motherboard recommendations. Lots of hardware knowledge, though it seems to windows oriented.