Looking for printer-shopping advice

The girlfriend and I are looking at buying a new printer. Our main criteria is that the printer must be usable from both Windows and OS X (and deliver nice quality prints, obviously). Things that would be nice in addition to that:

• Network connectivity, so we don’t have to have one of the PCs turned on to print from the iBook
• Color printing. Needs to have separate color/black cartridges in that case.
• Scanning ability

Any recommendations?

Update: We bought a Brother