Ynog, Intel Pro/1000MT (ca. $41) and Netgear GA302T (ca. $33) are inexpensive and reasonably architected 10/100/1000 boards that are supported by recent versions of Linux (back-ported drivers are available). You're going to pay as much anyway for a good board, might as well get gig while you're at it.
The 3C905 boards and Intel Pro/100 boards also work well, as do any REAL Tulip (21140, 21143, etc.) boards.
The RealTek, Tulip clones (Macronix, et al.) and such - the $5-$15 kind of NICs - do tend to work, but just not as well. The vendors of said boards switch chips all the time and between new chips and new revs, it's often a major driver headache ("oh, this month's D-Link DFE-123 uses the RTL-8139 rev. Q, which needs driver 1.42, just apply this diff..") - just spend a few bucks more and get a good board.