The critical figures are "RDS On", the drain to source resistance when the transistor is switched on by a suitable gate voltage, and the gate voltage needed for that resistance.
The other value that can be critical is the gate capacitance; that can be extremely high with power FETs, which means it takes either a lot of current or some time for the gate voltage to swing between the off and fully on levels. It's not too important with most simple on-off applications, but becomes rather critical with high frequency switching, which is why many high power MOSFET circuits use specialised high current gate drivers.
If the transistor gets too warm during the fade with your device, either C1 or R1 can be increased to reduce the switching frequency.
As long as it's over 100Hz or so it should not have any visible flicker, but the transistor will be fully on or off for a higher percentage of each cycle so dissipate less power. eg. You could try 1uF for C1 and see if that is still flicker-free.