My MTB/beater bike pedals are Shimano SPD's with what ever shoes fit your feet and budget. These pedals are relatively inexpensive, durable, clear mud and debris well and replacement cleats are readily available.
I have no personal experience with Egg Beaters but I've heard reports that the cheaper versions have serious bearing problems. The better ones seem well liked by the couple of people I know who use them.
BTW, Speedplay Frogs are wonderful road pedals but dreadful for off road use despite being advertised as MTB pedals. The cleats clog instantly in mud or gritty conditions.