A single 16 should run on a 30 amp, unless it's either a) faulty, or b) a hi-po unit wound to draw more current.
If your wiring and relay are sized correctly, try a 40 amp fuse. If that blows, you have a faulty fan.
BTW - initial inrush current can be several times the run current, not only to overcome static friction, but because it's an inductive load. That's why slo-blo fuses and circuit breakers exist.
Here's probably the highest perf 16" fan you can buy - note the steady-state
draw (26 amps), a 40 amp fuse is a must for this one.
And, here's a more normal high-quality 16" - draw is 22 amps, so a 30-35 amp fuse should be sufficient.
I'm already on record as advising against ebay specials - sorry.