This is a big topic. 3 to 4 MHz is not very high speed and 40V is very common, there are tons of MOSFET fit your needs. All MOSFET can switch way faster than this provided you can drive the gate. The main factor on speed of the MOSFET is the gate drive. Input capacitance and the drain gate capacitance are the main cause of slowing down the FET. At 3 to 4 MHz, you don't need to worry about the lead inductance and package of the transistor at all.
Some of the big MOSFET can have input capacitance into a few nano farad easily. You need a very high current drive to make it switch at any speed. BUT if you can drive it, you can make it switch fast. I did a lot of pulsing circuits with MOSFET, speed at rise and fall time under 1nS for a 100V transition driving a 10' coax. It takes a MOS driver DS0026 to drive a smaller MOSFET then drive the final big MOSFET!!!!
Back to your question. Depend on your requirement, get the smallest MOSFET possible that can handle the power of your requirement. Then look at the input capacitance and the drain gate capacitance. Calculate the miller equivalent input capacitance. Make sure you can drive the total input capacitance of the combined input and miller cap to get the speed you want. Look into MOS driver IC.