Almost any major-brand network laser printer made in the last ten years will happily talk to Linux, Windows, and Macintosh clients. I've had HP, Brother, Lexmark, Ricoh, Xerox, and more work just fine.
I would base your decision off some quick per-page costs (if you have high volume), ease of procuring supplies (does your existing office supply company carry the toner cartridges, for example? The admin assistant will love you if they do), and so on - with some quick checks in google with the model number and some relevant search terms looking for widespread reports of issues.
If the printer supports postscript (most network printers do, and usually also PCL/5), things will be even easier. The macs will probably be the easiest to set up; enter the printer hostname or IP, and OS X figures out the rest; even that may not be necessary as many current printers support Bonjour (auto discovery protocol.) If it's a 10.6 or 10.7 client, they'll download the drivers or PPDs if necessary. Earlier OS X clients may need PPDs or a driver downloaded from the company's support site to support all the printer's features (such as a duplexer unit.)
Brother makes about the cheapest network laser printers that are decent; I've had one for personal use for years with no issues, and we have one in our workgroup at work that has worked for 2 years without issue and light duty. Both are duplex, 1200dpi, and quite fast. FYI: Brother uses separate drum cartridges (HP and others use an integrated drum+toner cartridge.) That makes the toner cartridges cheaper/simpler, but you still have to replace the drum at some point.
If your staff print any confidential documents, HP sells some network printers with numerical keypads that make entering a PIN very painless. User prints (a PIN number is set in the print options), walks up to printer, enters PIN, and the job spits out. HR, legal, and finance people love that, but so might your sales staff if they're worried about other staffers poaching clients.
Another recommendation: keep around a backup printer, configured on everyone's machines, but turned off or with no paper; if you have to buy an old HP laserjet 4-series off Craigslist, so be it! If you yank everyone's personal printers and the new printer blows a gasket, people will get out the pitchforks with lightning speed. Buying the printer from a local vendor who will provide quick on-site support might be worth it, but having a second printer around as a backup is probably much cheaper and will give you time to get the printer serviced by the manufacturer.