I recently switched to Crank Bros Candy pedals, after several years on Shimano platform type SPDs.

I ride in a very muddy part of the world (and sometimes snowy) and found the cleats on the SPDS would get clogged with mud (I walk super technical stuff) and snow and be impossible to clip into and out of.

After a particularly bad session of the above a couple of weeks ago, I switched to the Candy's. there was a bit of a learning curve in terms of ease of clipping back in but otherwise think they're great. If the tread on your shoe is quite aggressive, you might need to shave a bit of sole off (with a rasp or really rough sandpaper) in order to clip in / out easier.

Good luck.