Fast Zombie is probably debatable whether it should increase CR or not. Not staggered and an extra attack is probably worth a lot more than DR 5/slashing on most creatures. I would say it is one average a CR + .5.
In addition, the table is HD 3 - 4 is a CR 1 creature. Obviously a 3 HD Zombie is less dangerous than a 4 HD (in general anyway) so 3 HD is probably toward the bottom of the CR 1 band, and 4 HD is probably toward the top.
Lastly, by having the advanced template included in the base creature, but not having the CR increase count once it becomes a zombie, you are still adding on the mechanical aspects (for the most part) but taking away the CR adjustment. What you mechanically have is an Advanced (Fast Zombie (Horse)) not a Fast Zombie(Advanced Horse).
So this is probably a creature that is right near the best of what should be considered CR 2, or possibly just makes it into CR 3. Especially with templates, the CR calculations are an estimate, not an exact science.
Still, a fast zombie heavy horse shouldn't be much of a challenge for a first level party, certainly not a TPK. I can't see this thing surviving a full round of the characters attacks unless they get quite unlucky. If it does get off a full attack of its own though, it does seem likely that it will drop, but probably not kill, one PC.
You could try this for some simplicity.
* Does the natural armor from advanced stack with zombie, or should I take the higher of the two?
* I feel logically I made a Fast Zombie(Advanced(Horse)), and if I applied the templates in Advanced(Fast Zombie(Horse)) order it would be CR 2 not 1. Can you explain how you came to the conclusion of your nesting explanation?
Basically your two questions are related. If you are adding the stuff from the advanced template on to your monster (increasing the stats, natural armor etc.) then you should be adding the advanced template to the challenge rating.
Basicically, whether or not the creature was an advanced horse that got fast zombied or a fast zombie horse that got advanced, if the stats are are the same, the CR should be the same. You shouldn't throw out the advanced CR adjustment.
The CR for a zombie is assuming 'normal' stats. It isn't perfect anyway since some HD is not a perfect proxy for how dangerous it is, and this is even bigger with the fast zombie, since number of natural attacks can make a huge difference now.
When in doubt, I add templates in the order that increases CR the most.
Of course, I usually wind up ignoring CR for the most part, but the above approach at least keeps it fair.