The generators can put out "dirty" power with fluctuations. I ran a fan on it once and you could hear the air movement change going up and down vs steady on regular AC power.
The generator can not make its output dirty on its own. To the contrary, hf-wise the output is way cleaner than the mains.
But it has rather high impedance, mainly at higher frequencies (harmonics), so a dirty load can make the generator voltage more dirty than the mains.
Mainly cheap generators are weak in this aspect. They are build with an expectation they would be used with just a single device as a load and there is an assumption the load is either clean, so wont disturb the voltage (radio,...), or tolerant towards the disturbances (e.g. power tools).
Definitely the fan is a clean load by itself (there is nothing to upset the voltage, it just has its impedance), so I doubt it could be part of the cause. The fan is sensitive on the voltage and mainly frequency fluctuacions, but these then must originate from the generator itself.
That fluctuating fan sounds to me like the engine rpm governor is oscillating (hunting; if it sees too low rpm, it takes it too long to correct the power and then it overreacts, causing the rpm to overshoot and then the same in the opposite direction), normally there is no reason why the fan should fluctuate at all.
The cause could be wear of the linkages so there is a significant play in actuating the throttle.
Or the joints and bearings are dirty so exhibit friction, creating a hysteresis. Mainly when the friction exceeds the tension of the linkage slack eliminating springs.
Or unstable operation of the engine itself (unstable mixture, clogged air filter, dirty air passages, sticky float valve, obstruction in the fuel feed, incorrectly operating choke, weak ignition, dirty, overheating or failing spark plug, dirty combustion compartment, loose magneto assembly, misaligned ignition timing, sticky internal engine components because the oil was not changed as it should be).
Or combination of all.