Anything Realtek-based should work nicely under both Windows and Linux. RTL chips like the 8111C are inexpensive and can be found in equipment from a large number of OEMs. Consequently, they are very well supported under a multitude of operating systems.
These NICs are sold under a multitude of names you've probably never heard of, like "StarTech", or sometimes under the RealTek name (even though RealTek just makes the chips). A gigabit PCI or PCIe NIC can be had for a little as $12-$15. The very cheapest chips may lack advanced features such as TCP offloading, so you may want to check the specs against the products section on RealTek's web site
If performance is an issue, Broadcom-based NICs could be what you want. Also very well supported under Windows and Linux, these chips are frequently used by server board manufactures. Companies like Intel, HP, IBM and Dell provide branded drivers for Windows, while the Linux drivers are part of the stock kernel. Windows drivers for high-end Broadcom chips often support link aggregation (bonding) and virtual NICs for VLANs. Linux, of course, has native VLAN support.