Now many people seem to dislike Crank Bros pedals, but I have a set on all my bikes and love 'em. Light weight (compared to Shimano), very easy entry and exit, excellent mud-clearing, and more float than other makes.
However they do need regular servicing and maintenance. I have some old SPDs that are still going strong (well my dad has them) and they must be 15 years old, never been serviced. You'll find that Crank Bros pedals need a bearing/bushing service every 2 years or so. Also when you buy them, give them a good internal squirt of grease – as they tend to come quite dry.
The Mallets are a great pedal, I have a set of the original ones. They support your foot very well, and are good if you need to ride unclipped, or without your cycling shoes. But they're nowhere near as grippy as proper flat pedals. Mine are 3 1/2 Years old now, and I did their first service just before Xmas.
As far as shoes go, depends on your riding needs, but you can't go wrong with the midrange Shimano offerings, such as the MT41s, or similar.