About the recipe:
Naan is traditionally made with yogurt to leaven it. It would have to sit for at least 4 hrs, or up to 12, depending on how warm it is. Yeast was not traditionally used in india (though is now), and baking soda is also a newer introduction.
Milk or water can be used interchangeably. Milk will make it a bit softer. This is just preference.
Egg is not necessary. Many people in India do not eat egg, so the default recipe would be without egg.
About how to cook them:
People at home rarely make naan -- it is something you would have out or at a wedding or somewhere with a tandoor. This is why there are so many variations -- it is just people adapting as best they can.
If you have a pizza or baking stone, you can get a really good naan by preheating the stone at your highest oven temperature, and just putting the naan onto it to cook -- this simulates a tandoor.
Otherwise, I have found the best thing is a griddle, again as hot as you can get it.
It works best if you keep the dough soft and roll it out with a little oil as thin as you can get it (it will "shrink back", so make it bigger than you actually want it).
General baking tips:
Baking soda will kill the yeast and yogurt bacteria. You can add it as "insurance", but do this at the end after fermentation. They also don't like salt (but salt will make your bread taste a LOT better), so also add that at the end.
I have not tried mixing yeast and yogurt, but it doesn't sound like a great idea. Maybe it is ok if you either reduce the amount of yogurt a lot, or add it again at the end after fermentation.