Madagascar has a unique position in that it's basically like Thailand in terms of its advancement, potential, etc. but with the position of Japan as an island and all (a resource poor island, as far as I can tell). Ethiopia's also a good comparison, but Madagascar is much more ethnically and religiously homogenous in that everyone speaks the same language although inter-Malagasy distinctions still exist. The Merina monarchy, when they embraced modernisation and didn't seclude themselves, looked to be on the cusp of becoming a modern state respected more or less by Europeans. Ranavalona II's brutal policies helped depopulate and weaken Madagascar. Either Radama I or Radama II, if they'd lived longer (one died of alcoholism, the other was murdered in a coup), could've greatly helped in modernising Madagascar and keeping it independent.
Now, we aren't getting an African Japan out of it, but Europeans would part with maybe a port or two as concessions, leaving the Merina monarchy independent as a whole. I'd also suspect they could have their own mini-Russo-Japanese War moment by defeating the Portuguese. Defeating France in a Russo-Japanese War-esque conflict would make for an awesome Malagasy wank, but if it's even doable at all, would require a pre-19th century POD probably involving earlier unification of Madagascar and everything going right for the forces who wanted modernisation. I'd think with France's colonisation efforts in the area, Madagascar would be more after their land, and could make a good ally for the Germans.
Everything I've read on the subject suggests that 19th century Madagascar could've had a far more interesting fate than what it got OTL. I'd say it's probably the most likely to avoid being colonised of any African country, right up there with Ethiopia if not higher.