Ica is near the Nazca lines (remember Chariot of the Gods?) and they are well worth seeing, but best from the air. From Ica you can bus to Arequipa (The White City) which is arguably the most beautiful city in Peru. The volcano "Misty" is visible from Arequipa. From Arequipa you can bus to Puno, on the shores of Lake Titicaca. There is a floating village there that the tourist boats will take you to. (There are some gift stores selling small statues, most of them pornographic, which unfortunately my 13 year old daughter discovered). There is a train running between Puno and Cuzco and I highly recommend the trip. It's high up in the Andes and passes through beautiful countryside and small villages. Cuzco has some other Inca or Pre-inca sites besides Machu Pichu (which alone is worth the trip) that are well worth visiting. Lima is a nice city. The Plaza Central (lots of photo ops there) and the Gold Museum are not to be missed, but there are many things to do and see. Miraflores, where I used to live, is a suburb of Lima with some very nice restaurants. The buildings in downtown Lima and other old parts have some fantastic balconies worth a few pics.
Ian is right about the thieves, but if you're careful you won't be bothered. I lived there for two years, and only once did someone try to rob me. Tried to take my wristwatch. Don't wear jewelery and keep your wallet and passport in your front pocket, not the back.
There are a lot of nice "pensiones" in Lima, sort of bed and breakfasts, and I recommend them.
Ian is also right about the altitude sickness ("seroche"), but it doesn't affect everyone the same. Smokers seem to deal with it better than non-smokers, probably because their lungs are used to a lack of oxygen. You can get pills for it, but I think they're mostly sugar. The natives chew coca leaves, so coca tea might help (no more of a hit than our tea, legal and available everywhere). Mainly don't exert yourself too much if the altitude starts to bother you.
If you want to see the Amazon, you can take a bus to Pucallpa, a days drive from Lima, longer on the bus. However it's a great trip across the Andes.
Take a Spanish phrase dictionary and learn how to pronounce the words before you go. Spanish is very phonetic - if you see it written you can pronounce it, once you learn the simple rules. Don't drink the water (the beer is good, but watch out for the Pisco, the local white lightening). Have a Pisco Sour though, it's the national drink.
It's been 10 years since I last visited, and I'd love to go back. Have fun!