How is the propagation delay of a logic gate affected by the amount of inputs (fan in)?
I can only answer in the context of standard CMOS logic gates.

For NOR and NAND gates, as the number of inputs increases you also increase the number of transistors that are connected in series. NAND gates of \$N\$ inputs have \$N\$ NMOS transistors in series while NOR gates have \$N\$ PMOS transistors in series. The series transistors have essentially the same effect as series resistors...they increase the time required to change the voltage on the load capacitance. Now you could increase the width of the series transistors to compensate for this, but that would increase the input capacitance of the gate and just move the problem to the previous logic stage.

Increasing the number of inputs for a NAND or NOR gate also increases the number of transistors that are connected in parallel, with all of their drains connected to the logic gate output. This increases the internal parasitic capacitance of the gate, further exacerbating the slower transition time. More wiring is needed to connect all of these capacitors, so even more parasitic internal capacitance.

So, if the propagation delay is proportional to \$R\times C\$, and increasing the number inputs increases both \$R\$ and \$C\$ then you could argue that the transition time is proportional to \$N^2\$. I don't think the relationship is quite that simple (not precisely \$N^2\$) but it is certainly worse than linear.