I went to Zermatt a few years ago. I did not take any lessons but my kids were in ski school - the official ski school that meets in front of the station - Swiss ski and snowboard school on Bahnhofstrasse. I did look into hiring a guide at the main guiding office on the main street - but for some reason I did not. sorry I don't remember their names.
I rented my skis from a shop right opposite the sunnega lift station. The best thing about them - was that they would store it overnight for free. They also have a store near the KM lift station. if you plan to ski KM the next day - they will have it transfered to their KM store - so you can pick up your skis from there. as i said - I do not remember the names - but google can help you locate the one I am talking about.
Also Ski club of Britain has a rep there - who offers a guiding service on most days. I hooked up with them one day, skied with a bunch of fun people and the guide showed the goods. you may want to look them up.
all the on mountain restaurants - at least the good ones - need reservations.