We spent 5 months in Grazalema a year ago. We did some hiking in the nature parks of Grazalema and Alocornocales.
As mentioned, the locals are friendly and helpful, but the language is a problem. We speak Castilian Spanish, but the accent in Cadiz is... well, difficult. And still, they are so proud of it. "Isn't it great! If we go 15 kilometres to Alcornocales, we cannot understand them either", they kept telling us with a broad smile on their faces.
Anyway, I prefer this part of Andalusia to Costa del Sol. And, there are some very nice hiking routes. You will find the route descriptions in English www.topwalks.net/en/index.htm
I recommend the routes in Grazalema. In Alcornocales you will need a permission to visit the most interesting routes (those are not included in the above mentioned website). The routes starting from Grazalema and Benaocaz plus the Villaluenga-Llanos de Libar route were our favourites.
Our favourite towns/villages were Grazalema, Arcos de Frontera, Zahara de la Sierra and Ronda.
In a restaurant you should try Gazpacho, Lechazo, Osso Bucco, Pierna de Cordero, Conejo, Champiñones Rellenos, Caracoles, Revuelto de Gambas, Bacalao, Sepia, Calamares, Mejillones...