unfortunately I cannot comment on Linux compatibility but I try to give a recommendation based on my personal experiences made in eight years of building PCs with VIA and NVIDIA chipsets.
if you see the broader picture, counting in my conversations and job experiences at various hardware stores / sellers the first thing that comes to my mind is that AMD CPUs (generally) seem to be more sensitive regarding MOBO chipsets, i.e. you cannot combine every random board with every AMD CPU without running into more or less grave issues. this probably holds true too for Intel but is more noticeable with AMD based systems.
I had very good success with nForce (2&4) based MOBOs with mature drivers and AMD. I wouldn't recommend VIA for this purpose anymore, simply because the trouble some guys had with such systems seems to be correlating to this combination. maybe it's gotten better over time now but I don't bother checking it anymore (saying this, my VIA KT3 Ultra2 plus AthlonXP is still up and about).
for a lower budget socket 939 system my current recommendation would be an ASUS A8N-E (around 80-85€ here) with an Athlon64 3200+ (115€) or 3500+ (140€) (Venice core, ...).
or Athlon64 X2 4x00 if you need / can afford it.
(in this case, you might also want to look at this)whatever you do stick to good MOBO producers like ASUS and MSI among others (if they are Linux driver compatible).
for further research I also would recommend well known trusted sources like Tom'sHardwareGuide.
just remember that AMD will continue to produce CPUs for this socket but won't do so forever. well, by the time you would need more horsepower the AM2 socket together with DDR2 memory will probably be a bit more attractive concerning good performance memory etc.
hope that helps a little.
edit: spelling