Despite the cautions from the UK Foreign Office and no doubt the US State Department as well, I think you will have a blast and I will try to offer a few ideas based on my trip. I never heard of the power struggles in Madagascar impacting any tourists. I don't think tourists actually tour the presidential palace, although you can see it from a road and it is huge, supposedly with an entire zoo back there. (could be a rumor) But to my knowledge the very occasional demonstrations or riots or whatever you like to call them would not affect the traveler. Madagascar has one of the weakest currencies in the world and is protective of its tourists. People are friendly. The only issue I had with walking to the store or post office or wherever in the capital was people trying to sell me stuff. Crime etc. was not a concern.
While we did have a tour guide, it was because of the specialized nature of our trip. Dr. "Lily" of the Madagascar Peregrine Fund took us into areas where we could find specialized species, such as the Madagascar Serpent-Eagle In addition to specialized bird tours, offered by many companies, the other popular type of tour I saw was the photo tour, mostly filled with Japanese tourists carrying special equipment for photographing the unusual lemur species. I could find out if the Peregrine Fund is doing any more of these trips, but I think that November would always be the month, not September.
However, I got the impression that most of the younger visitors just "showed up" and booked the tours of their choice once they arrived in Madagascar. I didn't see individuals renting cars, what I saw was, people joining groups of 4 or 6 in a van with a driver. There are VERY frequent road checks of the driver's credentials and license to transport tourists, so I think you can feel easy about that.
At the national parks, even if you bring your OWN guide/driver, you are generally ALSO required to stay with the guide that they assign to you. This is not a bad idea, as it guarantees that locals get and keep jobs and are invested in the protection of the wildlife. Also, some of these local guides develop deep knowledge of some of the species, how they live and how they can be found.
As a honeymooner, I'm sure you will want to arrange for a visit to Tritriva, the Lake of the Lovers. The story is the Madagascar version of Romeo and Juliet, and when you see the cliffs of the lake, there will be few questions about how the lovers tragically ended their story. Many tours will bring you to this area for the glorious sunsets.
I have a very long diary about my visit to Madagascar, if you go to this page:
http://peachfront.diaryland.com/madapt1.html
and scroll down to November 13, then you will see photos of Tritriva (that do not do the place justice) and get some idea. At the time we visited the Madagascar Kestrels were engaged in feeding displays and other breeding/bonding activity there, which added to the atmospheric and romantic nature of the scene.
If you speak both English and French, you have a decided advantage if you do any independent travel around Madagascar, however even if you don't hire a "guide" per se, then if you rent a car, I think it will come with the driver who will also speak Malagasy. This is something you should double-check for yourself, as Dr. Lily always made these kind of arrangements for us. Your hotel or hostel will help you book tours and probably at a very reasonable price, if you have no specialized interests that you need to book in advance.
The other poster's comment about arranging for a luxury stay in the Seychelles is a kind way of saying that, as far as we know, there are no true 4 star accommodations in Madagascar. This is a destination for the nature lover and the adventurous person. It is one of the poorest countries in the world, with one of the weakest currencies, so it is a DIFFICULT destination for the person with a picky, specialized diet or some other high maintenance lifestyle. There is a French influence on the food, but not in a good way. Rather, in a way where it's coffee and cold French bread with butter and jam, and that's breakfast. Also, at the time of my visit, November 2007, most parks had electricity in the cabins for 2 hours in the evening.
On the other side, though, people are friendly, prices are low, and you will see wildlife and settings that you simply can't see anywhere else.
I did not go a very efficient way, as I used miles to fly WBC on KLM to JNB and spent a few days either side of my tour there. To book my flight from JNB to Tana, I had to go to the Air Mad website and order my tickets from Paris. They were paper tickets and were delivered by DHL exactly when I was told they would arrive. But I had to wrestle with the webform a little, because it was mostly in French, which I don't know. You could buy the same ticket from South African Airways, and it was on the same plane, but it was $300 more, so I was willing to just go slow and use the French form. They may have an English webform by now. Maybe they even did then and I just couldn't find it.
Air France goes straight from Paris to Tana, and the other people on my tour took this flight. With only 2 weeks to work with, however you go, I would strongly suggest traveling from North America business class rather than trying to make this very wearying journey in coach.
The other parts of my diary are Part 2:
http://peachfront.diaryland.com/madapt2aaa.html
Part 3:
http://peachfront.diaryland.com/mada3maso.html
Part 4:
http://peachfront.diaryland.com/beranda4.html
This is more of a Lonely Planet destination in some ways, than a Flyertalker destination. You can read the Lonely Planet forum about Madagascar and get more ideas. It's also a gemstone destination, and I don't know the ins and outs of leaving the country with gemstones as I didn't visit the mining areas nor did I buy any gemstones. You should check on this before you buy anything, to make sure you are taking the gems out of the country legally. There used to be a gemstone buyer who sometimes posted on the Thorn tree at the Lonely Planet. I *think* his name is Rory, so you might look out for him if you think you might be buying a special gem there. I think the Ocean Jasper may be mined out, as I was surprised at how little "quality" Ocean Jasper I saw in the market at Tana.