The fact of the matter is that you're printing on a colour laser printer that has just about the same resolution as a mid-level mid-1990s inkjet printer. It is incapable of producing photographic-quality continuous-tone images.
The printer's maximum resolution is only 600 by 1200 fixed-sized dots per inch, with only four available toner colours. If your image is printing at 300 pixels per inch, then there are only eight dots (nine levels, including white, per colour) available for each pixel. That's obviously nowhere near enough for a possible 8 bits per colour per pixel, so some pretty wild dithering has to happen to represent most of the available colours. Dithering can work wonderfully well for business graphics (large areas of solid colour or simple, predictable gradients) but it's going to stick out like a sore thumb on photographs or photorealistic illustrations.
In black and white mode, each of those pixels is either black or white; there is no continuous grey or colour for the printer to worry about, so no dithering needs to happen.
As a contrast, a typical small-format graphics or photographic inkjet printer will operate (in anything but "draft" or "econo" mode) at at least 1200 by 1200 variable-sized (at least two sizes, often four) dots per inch, and will use more than four ink colors. (Business-class printers or the $40 special may only use four ink colours.) When running in high-quality mode, they will use many more dots per inch. That means that there are an awful lot of available ink dots per image pixel, and dithering (while it is still necessary) is kept to a minimum and really can't be seen without a loupe. And 4-colour process presses (offset litho) may use screens coarser than 200 lines (fewer than 200 dots per inch per colour), but those dots are almost infinitely variable in size, so it's relatively easy to produce exactly the right colour at any given spot on the page.