Quelques suggestions et réflexions sur ce que je connais.
Déjà pas de souci de transport il y a des grands bus confortables et climatisés (un peu trop, gaffe à ne pas attraper une angine)
- vous allez descendre au S sinon je vous conseillerais au NW São Luis qui est très intéressant ainsi que la région.
-
Fortaleza : pas folliche comme ville
-
Natal est à voir
- Jão Pessoa aussi
-
Recife.
Olinda est la vieille ville, à voir, au N. Il y a des hôtels.
-
Salvador, bien sûr, et il y a une sympathique excursion depuis le matin à faire sur la baie avec un bateau qui vous emmène en face à
Itaparica (avec un bon restaurant à midi)
-
Fernando de Noronha est un île réserve naturelle très jolie. C'est un peu au N d'elle que l'Airbus d'Air France s'est crashé. A l'W se trouve un joli (d'après les photos de Google Earth) Atol das Rocas, mais je ne sais pas si on peut y aller.