Shimano gear is good. You can't go wrong with a pair of
M520 SPD's, I've been using them for years, they're dead easy to clip in and out of if you adjust the tension properly and they last for ages (current pair are about 5 years old). Any 2 bolt mtn pedal will be fine though (ie crankbrothers, Time ATAC, SPD) and will give you the recessed cleats you're after when used with a mtn bike or touring shoe.
Time ATAC are also held in high regard, and there's the newish
Look Quartz system (though there seems to be mixed reviews on these), but I wouldn't get the Crank Brothers Smarty. I don't think the release tension can be adjusted which isn't ideal for a beginner (it's a good idea to have this set pretty loose till you get used to it), and if you read some of the reviews they seem to have a tendancy to fall apart pretty quickly.
Specialized shoes are also very good, I've a pair of the road shoes and they are excellent. I'm sure the mountain bike shoes are just as good. Any mountain bike shoe will have a 2 bolt cleat fitting so will fit just fine with any mountain bike pedals like those mentioned above.