This is a question that may be a "mystery", or one that is nearly impossible to answer, hopefully you guys have some good ideas about this. Why did Jesus come at the exact time he did? Why didn't God show Him at another time, when ancient people were believing in other false Gods?
Answer
There is no precise answer in scripture why Jesus came when he did. We know from Galatians 4:3-5 that it was the proper time. "Even so we, when we were children, were in bondage under the elements of the world: but when the fulness of the time was come, God sent forth his Son, made of a woman, made under the law, to redeem them that were under the law, that we might receive the adoption of sons." Why was then the "fullness of time" as the King James Version translates it? As you say, it may be a "mystery." There have been several theories, all seeming to be valid. I stress that what follows is the ideas of men, and not scripture except where quoted to support a theory.
First, it was a time when the Jewish nation was finally ready. They had gone through years of falling away from God. After returning from captivity in Babylon about 500 years prior to that time they had never gone again after idols. The nation was politically and religiously divided in such a way that it was a certainty that Jesus would be executed, which was a necessary part of God's plan.
Second, it was a time when the spread of the gospel would, for the first time since the tower of Babel, be an easy matter. Greek was the universal language; everybody of consequence could understand Greek. However, it was also a language that, in the dialect in which the New Testament was written, would soon be dead. That meant that the meaning of what was inspired by the Holy Spirit would not change. The Roman army had established the best world-wide system of roads in history, and kept them safe, making travel easy. Because of the relative ease of travel and the uniformity of language Paul was able to say in Colossians 1:23 that the gospel had been "preached to every creature which is under heaven."
Also it was a time when the Jewish faith was known throughout much of the world. God had established the law of Moses to serve as a "schoolmaster to bring us unto Christ, that we might be justified by faith." (Gal 3:24) Because there were Jews in almost every major city of the Roman empire (such as Ephesus, the second largest city in the world), many people knew of the system of sacrifice established in the law. That knowledge made the sacrifice of Jesus the Christ more understandable among the gentiles, helping them to accept the gospel.
There may be other reasons this was the right time. These given may or may not be valid. All we can be sure of from scripture is that God says it was the perfect time.
As far as sending him at a time when people were believing in other false gods, there has never been a time when false gods were not worshipped. The Romans and Greeks had a large number of gods. Before them were many others. Since them have been the false gods of money, humanism, science, and many others. The fact of false gods probably had no bearing on the timing of Jesus' coming.