I'm pretty happy with the older HPs (4600/5600 Series)... toner can be bought very cheaply, and the printers are pretty reliable. The PrinterWorks sells used ones at a pretty heavy premium, but everything we have ordered from them has been in excellent (like new) condition. eBay usually has a few of them pretty cheap. They are very fast as well (single pass 4 color printer). There are pretty cheap network options for it (internal and external), and changing a non-duplex one to a duplex one just requires a new formatter PCB (the actual hardware is in all models... the controller is the only difference). There are also a bunch of other finishing and additional tray options, and native OS/2 support in the PS and PCL driver sets.
We installed a Lexmark c500 Series at a client which I am very fond of (great prints, decent number of prints on a cartridge)... but the cartridges are kinda expensive (though there may be aftermarket ones that are cheaper, or wholesalers who sell them cheaper). They supposedly support OS/2 (drivers on CD and Lexmark's site), but we have not tried the OS/2 support (it's hooked to a customer's Windows XP client station, and no where near their OS/2 server). This printer also is very fast (it too is a single pass 4 color printer). It comes with duplex and network options.
For the Lexmark, dont bother checking their OS Compatibility List (it makes no mention of OS/2). Instead, go to drivers, select one of the c500 Series, and check it's driver page. Linux and DOS also get such treatment on their OS Compapitibility List.
Robert