Our Canon S750 inkjet was getting long in the tooth, and never really had good Linux support, the quality with the S800 driver was OK, but to get the highest quality prints required the use of a proprietary driver from TurboPrint.
We are replacing it with a Xerox 6130/N color laser which I got from newegg.com plus a free Canon PowerShot SD1100 IS Blue 8.0MP digital camera. The Xerox 6130/N while it doesn’t explicitly list Linux support, supplies PPD files on the CDROM and works great with Fedora!
The printer has both USB and Ethernet. I chose the network setup as it was the easiest to work with. I love having a laser printer at home, it is amazing how much more crisp the text and graphics are compared to the old Canon.
If you’re looking for a good color laser that works with Linux, I highly recommend the Xerox 6130/N.