I can't seem to find it being sold any more, but I'm really happy with my OKI C110 which I have hooked up via USB to my router which is running OpenWRT and can route print jobs with p910nd. It means I can print with anything that can use the standard printer driver (linux and Windows) and I just have to point it to the TCP address. It also means it's a lot cheaper because the printer only has a USB port (It's a $99 colour laser printer).
I've also used the Brother DCP-7065DN (which has a wired ethernet interface) and that works well with Linux. It doesn't do colour, but it has a page scanner with a sheet feeder. I was able to use the SimpleScan program in linux over a network to scan (even with the sheet feeder!). Brother provides linux driver binaries. Staples seems to have it now for $179.