Go clipless and never look back. I've had a number of different setups but always end up back at a SPD pedal from shimano. Currently it happens to be the xt 785 trails. Never been a fan of multi release cleats. Like slappy I found the to be very unpredictable - IMHO a pedal with adjustable release tension is the best bet. Set them light at first so you can bail easily while learning to kick your heels out to release. Increase the tension as you get used to them.
Shoes are personal preference. It's going to depend on what fits you best.
Slapheadmofo Leisure Team