One of the most difficult things to print is exactly what you're attempting. You might farkle around with profiles and profiling equipment and you might even clean it up some. Unfortunately you're dealing with a CMYK printer, which prints CMYK, not just K. That being the case, your RIP tries to interpret every intermediate tone along the way in CMYK, not just K.
You can often mitigate this most basic characteristic of a CMYK printer by making your gradient into a bitmap and then adding just a wee bit of noise to it. The noise prevents a smooth and often fraudulent progression from one tone to the next and can, sometimes, make things a lot better. Your mileage may vary.