Mali through Burkina Faso is quite easy overland, by the way. You could start in Senegal and go through the Gambia on the way. A lot of people also then go to northern Ghana and on through Togo and Benin.

For the South Pacific, all roads go through Fiji. I've been to both Kiribati and the Solomon Islands and the only workable flight schedules require a day or two in Fiji in between.

I've been fascinated by the Comoros (and Mayotte, which is a French dependency) for some time, but that seems complicated, with very limited flight routes and political instability. There is a reason it is nicknamed coup-coup land.