I have no experience with Brother. I find that Lexmark usually makes good printers, but their business practices bother me, so I don't buy them anymore. I have had very good experiences with Xerox (nee Tektronix) printers. The 6110 is actually new as of January, so don't worry about consumables being hard to find. That said, it's their low-end printer. The only language it supports is GDI, which is a Windows-internal language. This used to mean that it was a Windows-only printer, but Xerox explicitly supports Mac OS X and even Linux. The manual for it even has a reasonably comprehensive troubleshooting section for Linux, talking about things like CUPS, Ghostscript, Samba, etc., so I'd bet that the support is pretty good. And the Mac section is also pretty good, but they have fewer variables with a Mac, so it's shorter than the Linux section.

Personally, I'd go with this one, unless duplex was a requirement. Then again, that is in part due to my lack of experience with Brother and my refusal to buy more Lexmark products.

Oh, I also prefer laser printers, as toner doesn't magically disappear just sitting there like inkjet ink seems to.