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.