I half expect the printer is making some excuses. They’re not totally made up — gradient banding is always a real thing as are color density variations in those gradients.
However, I’ve never heard of gradient banding referred to as “fountain steps,” but, hey, terminology differs from place to place. Gradients are not smooth, continuous transitions. They’re a series of steps that, under the right conditions, can be seen. I’ve also never heard anyone cite a difference between the steps in a gradient between a Mac and a Windows machine. There are those here who know more about the technical end of them than I do, so I’ll let them explain. @PrintDriver, where are you
As for the greys heading off into green, any neutral grey composed of the four process colors is apt to skew off in one direction or another. A grey composed of, say, 10c, 10y, 10m, 10k should produce a nice (but lifeless) gray. However, all it takes is one of those inks printing slightly darker or lighter to skew the color off visibly in that direction.
In a 4-color process grey gradient, at each point in the gradient — especially at the very light color densities — you’re apt to get one of the colors stepping down a notch or getting darker or lighter at slightly different rates than the others throughout the gradient. This will end up causing an the unwanted rainbow effect that you described. For example, if a two percent magenta suddenly drops out between two and zero percent in the gradient, that portion of the gradient will appear greenish. in addition, the printer RIP might not get the gradient perfect across all four colors or the dots on the litho plate might disappear at light densities or the droplets of ink sprayed onto the paper in digital printing might not be exactly calibrated perfectly at all densities. There are a half dozen minor errors that can affect neutral 4-color process greys.
You really should avoid neutral greys in 4-color printing — not only in gradients, but in general. It’s much better to create a grey composed of different percentages of the process colors. That way, those one- or two-percent differences in ink density won’t make as big of a difference and won’t be nearly as noticeable. And asking for all the colors in 4-color process gradient to evenly thin themselves down to white, um, you’re asking for problems.
As for minimizing the banding that occurs in just about any gradient, there are ways to do that, like dithering and adding noise, but like I said, others here likely have better techniques and know more about it.