Lonnie, enjoy your travels! We were in Peru (Lima and Cuzco, also Iquitos in the upper Amazon) in 1995, too far back for specific recommendations. Be sure to get seviche in Peru, though - the corvina is best. They join Chile, Ecuador and Mexico in claiming to be the original source of the stuff, and I expect they are all right.
Lima's "international" district for the well-off, Miraflores, is pretty much like the "nice" shopping district in every major world city, and just about any local resto there will give you a sample of the nation's flavors. Sorry I can't offer any specific little amazing hole-inna-walls, though.
Cuzco seemed to offer either restaurants designed for American tourists or hole-inna-walls. We ate at a little rosticeria there that had awesome chicken, but I made the bad mistake of dipping my fries in a communal mayo pot ("It can't hurt me! They're nice people, and we've been here long enough for my biota to get used to it!") ... and the ensuing Montezuma's revenge wasted a whole day of our trip.