Why am I cooking MOSFETs?

Your problem is the gate drive voltage. If you look at the datasheet for the STP16NF06, you'll see that the 0.08 Ω Rdson only applies for Vgs = 10 V, and you're driving it with only (a bit under) 5 V, so the resistance is much higher.

Specifically, we can look at Figure 6 (Transfer Characteristics), which shows the behavior as Vgs varies. At Vgs = 4.75 V and Vds = 15 V, Id = 6 A, so Rds = 15 V / 6 A = 2.5 Ω. (It may not actually be quite that bad, due to some nonlinearities, but it's still more than you can tolerate

ESD could also be a problem: the gates of MOSFETs are very sensitive, and there's no reason that the Arduino (whose microcontroller has ESD protection diodes) would also necessarily be affected.

I'd suggest getting a MOSFET with a low enough threshold voltage to be fully on at 4.5 V. You can even get MOSFETs that incorporate ESD protection on their gate.

The point about the gate voltage is valid, but if the MOSFET is not heating up, I'm not sure that is the actual culprit here.

16 meters of 12 V LED strip driven at several amps is going to have a significant inductance at typical PWM frequencies. This causes voltage spikes at the drain every time the MOSFET turns off. These spikes are short in duration, but the voltage can be many times that of the supply voltage.

The solution to this particular problem is to add a freewheling diode (Schottky) in antiparallel with the LEDs, between +12V and drain, just like you would with an electric motor or other inductive load.

One further thing to check.

This looks like an experimental setup connected to one or more PCs and/or plugpack power supplies.

This often yields an environment that is nowhere directly referenced to earth ground, or referenced to it at some point in the circuit in an uncontrolled manner, especially when a laptop computer with a two-prong-connected power supply is used.

Common "lightweight" plugpack switching power supplies tend to give you output rails that actually have a high-impedance AC potential relative to earth, at half the mains voltage, superimposed on both poles. This usually goes unnoticed because the load is either completely floating (a plastic cased accessory), or has its ground tied firmly to earth ground (a desktop PC), and the impedance is high enough not to hurt you (unless you hold a wire to your tongue, near a vein ... don't, even if it should be safe.).

However, in a test setup like this, it can mean half mains voltage appearing in the wrong place - and 60V or even 120V (actually, a peak voltage of around 170V in the worst case...) can be enough to damage the gate of an unprotected MOSFET if some other electrode is earth ground referenced in any way (eg by a well grounded person touching the drain or source circuit)..