If you go with any recent Intel or AMD processor, you should be fine. Stay away from other manufacturers. I won't get in the Intel vs AMD flamewar, other than to say I using an Intel Core i5 2500k and it runs excellent on Linux Mint 11 and Debian 6 (with Stable repository) without problems. Not sure about LMDE (only ran that for a short few weeks).
Don't bother with a graphics card unless your wife wants to be able to play heavy 3D games (titles few years old will play fine on Intel Core i5 2500k or Core i7 2600k, for example). Any other game will run fine without a graphics card (all Intel Core i3, i5 and i7 have a built-in graphics chip).
I have a microATX motherboard from ASRock, the ASRock H67M-GE/HT. It has most modern features (DisplayPort, USB3 with back and front ports, SATA3, etc.) and it has been stable as a rock for me. The BIOS is fast and you can configure everything without Windows (not so for some ASUS motherboards). I've also built some PCs with Intel motherboards. They are stable and run problem free, but the BIOS is not as configurable as with ASRock. I wouldn't buy Intel motherboard again as the BIOS really is a weak point.
As for Linux support, I don't think one brand is better than another. The problem with motherboards is they are assembled from various chips and components. Motherboard A from a certain brand might work flawlessly, but motherboard B of the same brand might be a nightmare to get working. I don't know of any brand that actually provides real support for Linux. Best to research your motherboard in advance and see what Google is saying about other Linux users using it. That also means you shouldn't buy the latest & greatest model; as not enough Linux users might have used it yet for you to find problems other have had...