I didn't think much of Cusco when I got there - a small mountain town, heavily geared for tourism.
Cicciolina changed that. Maybe it is the amount of tourists that pass through the town that make it possible, but what saved Cusco from being a boring town that happens to be surrounded by Inca ruins was one fantastic Italian restaurant with great food and wonderful atmosphere - Cicciolina. It is impossible to list anything wrong with the restaurant: The food is great, the service is great, the atmosphere is great, even without a booking you get a table within minutes, etc.
Just go there. The prices are great, too.