Parque Estadual do Cocó (Cocó Park), the largest natural urban park in Brazil’s north/northeast region, is a great place for a green, shaded run on softer trails. The large green space in the eastern part of the city is a conservation area, with ~2.5 km of trails. At the south end of the park is Rio Cocó, where one can catch a boat tour. Pro Tip: Great place for a shaded run when it’s hot! 

The trails are a natural surface — dirt and wood chips — and run underneath a nice tree canopy. It’s very pleasantly shaded. Overall, one can stitch together a ~5 km run combining the Trilha do Cocó and the Trilha do Lago (trilha=trail), plus a short spur trail down to the river. This does involve some out & backs along the trails. 

Add-On: The Cocó neighborhood, north of the park, is a decent area to add some mileage. While not especially scenic, there are some fairly quiet streets and there are good sidewalks.