If you really want to kill two birds with one stone I strongly suggest you go through South Africa, but that may be slightly more expensive.
You can fly all the major airlines to South Africa, (KLM, BA
, Lufthansa, Emirates, etc and obviously South African Airways), and then fly Air Madagascar / Air Austral / Interair from JNB
One good thing is that onyour return trip you when you go through South Africa, you can visit Cape Town, Durban, the countryside, etc. Its a really beautiful country. Its worth the price if u wanna go on a holiday to 'africa'
One other major point is if you are more comfortable in an English environment, South Africa should be your gateway too.