Keep the connections from microcontroller to MOSFET short, both gate and source. The gate-source capacitance is relatively large and wires act as inductors. The combination of long wires, \$C_{GS}\$ and sharp edges will introduce ringing (oscillations). Instead of turning the MOSFET quickly on and off, it will spend a relatively long time in its linear mode of operation, where a lot of heat is dissipated. Low \$C_{GS}\$ and low \$R_{DS,on}\$ are good properties to look for in the datasheet.
To dampen ringing, a small resistor 100~220\$\Omega\$ in series with gate is good practice.
Websites like digikey.com and mouser.com have parametric search, which makes selecting a transistor that answers your criteria quite a bit simpler. Always check local availability of your parts and prices can vary a lot with various shops.