When I was in Lima this past November, I stayed at Hotel Antigua Miraflores and highly recommend it. The room was pleasant, the public areas full of character, the staff very friendly and spoke English well. Very reasonable rates with a good breakfast included. Tripadvisor reviews.

Although if you're going to be in Lima for just a very short time, like arriving late evening and leaving for Cuzco the next morning, the Sheraton in the center city would be a good option, as they have a free airport shuttle. - which would save you at least $20 in taxi fares. Octopustravel.com has good rates for that hotel which include a buffet breakfast.

For Cuzco, I would suggest the Ninos Hotel. Tripadvisor reviews.