Have you considered the luggage storage option? Here is the link:
Left Luggage @LIM
I suggest you also to check this thread:
http://www.flyertalk.com/forum/peru/...into-town.html
JohhnyColombia even posted some interesting pictures.
It all depends on whay you enjoy the most: museums? walking tours? archeological sites? Shopping? bohemian neighborhoods? I suggest you to check the mentioned thread (and I think there are others, too) and then ask more specifical questions ig you have any doubt, I'll be glad to help you. BTW, when are you coming? Depending on the season the suggestions may vary too.
About taxes, if your ticket doesn't included, you must pay just entering the terminals, right before the X-ray checks:
LAP Taxes