Oliver,
I purchased a Lexmark Optra E310 laser printer recently because it was a great printer for the money ($399).
Since I use a Wallstreet G3 PowerBook and USB cards aren't readily available yet, I hooked the printer up to my old NeXTStep PC via the parallel port. NeXTStep automatically creates an LPR queue.
To print to it from the Mac, I just used the Desktop Printer Utility, which is built into Mac OS 8.5. It lives in the Apple Extras folder. It was really easy to create a desktop printer that connected to the LPR queue. And with the exception of nasty PostScript errors in a few high-end programs (PageMaker, Photoshop, Canvas), eveything works fine. I think the PS errors in my case are NeXTStep-specific, so you shouldn't have a problem with Linux or something else.