The area around Arequipa - like the whole of the Peruvian Andes - has some great trekking. The issue you may have, though, assuming you are a solo traveller, is that it is difficult to find group treks to join. And generally, the longer the trek, the harder it is to find others to join. So, as you’ve found with Colca Canyon, it’s generally the one or two-day expeditions that are advertised.
Owing to the higher number of travellers, Cusco has more group treks to join. Although Cusco, Sacred Valley and obviously Machu Picchu are very busy with tourists, you wouldn't call the treks themselves 'saturated' – with the obvious exception of the Inca Trail and perhaps the "Inca Jungle Trail" which is fun but can feel a bit like a production line. All the other treks here will get you plenty of solitude and are all highly recommended.
Another trekking hub is Huaraz, in the Cordillera Blanca and Huascaran National Park. You could spend the rest of your life hiking and climbing in this area! The down side is it's hard to find group treks here. The 4-day Santa Cruz trek is one that many Huaraz agencies offer in a ‘pool’ service, but it’s hard to know the quality of guides, equipment, vehicles and food. If it is cheap, corners will likely have been cut to keep costs down.
Finally, further north, there are a lot of treks to be done in the Chachapoyas region. The Andes here are not as high as further south, but you get largely-unknown ruins from the Chachapoya culture and are unlikely to meet other tourists. Given the small number of visitors, all the treks here are in a private service, but the lower entrance fees and lower demand mean that the cost of these is similar to a group trek elsewhere … and you get the full attention of the guide and crew.
