Both walks, indicated on almost all maps of Madeira (including the free one given out by the tourism office), are delightfully scenic.
The maps of Madeira are all incredibly detailed even if you take the free one from the tourism office.