Hey Terry, welcome back! Sorry to hear about getting laid off. I was too, but it's an opportunity.
A relay will make no difference to a fuse unless the fuse is too low in value. All a relay does is lower the current through whatever the controlling device is. All electric motors use considerably more current to get started than they do once they're spinning; in electonics we call this "stall current". It is normally anywhere from double to triple the normal current draw of the electric motor.
A slow blow fuse is exactly that: it will handle a short-duration overload but will open if the overload is longer. A slow blow fuse may prevent your fan fuse from blowing the instant the fan is called to action. While having nothing to do with blowing fuses, relays are always a good idea for running heavy loads from a low-rated controlling device.
Longer term, for your cooling issue, you didn't mention if you had a shroud, or whether you still have the stock pig radiator. A shroud may solve the issue by itself if you don't have one. From a physics standpoint, it is always better to pull the air through the radiator than push it. A pusher fan will always block some flow, and is more difficult to use a shroud with. It's all about flow through the radiator, and surface area. With the cummins, you probably have more heat to dissipate and may benefit from a larger radiator or more cores for more surface area.