[franken]

If the FL gets hot when the fan is on, then the red feed to the fan relay isn't powering the fan... I'll bet the wiring is off and all the fan current is going through the FL. I have a big air compressor in the garage that had the starter (big relay) and pressure switch wired so that all the 27A motor current went through one 3A contact in the P-switch. And it ran that way for many years. The point is, its not hard to get the wiring a bit off.

I'm pretty sure you aren't using a 16 FL. My understanding is one size smaller (larger number) than the load it protects, so yes, 12AWG FL for a 10AWG wire.
If the FL isn't in the run from the battery to the fan relay, the issue is something else.
I didn't make it too clear, but the voltage measurements are with the fan running.
That difference in voltage by changing where you put the meter ground says you have sketchy grounds.

Finally, what the fan is set at is no indication of what the fan is actually doing.