We drove through Mozambique a few years ago on our trip through Africa. The country was colonized by Portugal and the attiude of the people is much like the Brazilians... a lot of life and energy. We called it Latin Africa. Since the end of the civil war South Africans have been moving across the border and building Backpackers/Hostels and beach style budget accommodations in Moz...
The diving is wonderful...beautiful fish, coral reefs.
Many of the roads are new, being built by South African contractors....two lane, tarmac with a small shoulder. Here is the route we followed.