The Persian Empire, arguably, was the first to not mandate one particular religion.

Cyrus the Great was Zoroastrian and did make Zoroastrianism the state religion. However, he had a very laissez-faire form of governance. He allowed indigenous leaders of the lands he conquered great autonomy. The area will keep their culture and religion and stuff, and pay tributes to the Persians. Because Cyrus didn't rule with an iron first, he didn't force conversion.

That being said however, being Zoroastrian would have helped a lot if you were trying to win his favor. While not explicitly mandated, a Zoroastrian will rise in the ranks much faster than someone who wasn't.

I believe that your professor was thinking of the text of the Cyrus cylinder. However it is a slightly more difficult issue than the texts reputation would have you think. In short the cylinder represents how we create useful messages for our time out of ancient sources irrespective of their original context. So we read it as if it is a declaration of religious freedom for Jews in Persia (hence a modern message of tolerance). However it really only shows Cyrus' ability to impersonate local elites (with no direct mention of Jews). There may be more evidence of Persian religious tolerance than the cylinder but I am unaware of it. I am just saying that a lot is placed on a small amount of evidence to create a politically useful modern message.

The question of whether or not the Persian Empire of Cyrus to Darius III was Zoroastrian, Monotheist or religiously tolerant is complicated at best, as is any discussion of what exactly "religious tolerance" means in the ancient world. This thread with myself and /u/Daeres discusses Achaemenian religion and the problems of calling it "Zoroastrian": http://www.reddit.com/r/AskHistorians/comments/1l70mz/around_the_year_500_bce_were_the_jewish_people/

Regarding the broader problem of religious tolerance and the state, it's probably helpful to frame it as a distinctly 'modern' problem. The confessional state, whether Safavid Persia the England of Mary I, is very much a product of the early modern period. Even in the middle ages, which people often see as the classical era of faith reigning supreme, the religious hierarchy and the state are not always in alignment and can and do butt heads. Nor did religious power always coincide with secular power dynamics; in some cases it was religious minorities who were more under the control of their religious hierarchy when that religious hierarchy was able to claim to represent said minority before the state. Turning back to the Ancient Near East, policing the religion of one's citizens was a largely pointless process for the simple reason that Babylonian or Hittite or Assyrian religion did not generally make the same universal monolatrous claims on their own behalf that Judaism or Christianity or Islam do on their own behalf. These states could and did expand their pantheons(in the case of the Hittites, to absurd proportions) or sponsor local religious rites, such as when Assurbanipal renovated the major southern Babylonian shrine at Ur or when Esharhaddon restored Babylon. Even when action was taken against a local cult, it could and was framed as action on behalf of the god of that cult. The destruction of Babylon and the taking of the cult image of Marduk to Assyria under Sennacherib was framed by his son Esharhaddon as the will of Marduk: Marduk had become angry with his city and left for Assyria and this was what allowed the cult image to be removed. Earlier texts also frame the abandonment of cities temples as the will of the gods; the Lament for the Destruction of Sumer and Urim casts the destruction of Ur and disruption of its rituals of kingship and cult as a divine decree dependent on the gods abandoning their shrines in that city.

The most famous piece of evidence concerning the active suppression of cults from the pre-classical Near East, the Daiva Inscription of Xerxes, largely points towards a similar case. The relevant passage is as follows:

King Xerxes says: when I became king, there was among these countries one that was in rebellion. Ahuramazda bore me aid. By the grace of Ahuramazda I smote that country and put it down in its place. And among these countries there was a place where previously demons (daiva) were worshipped. Afterwards, by the grace of Ahuramazda I destroyed that sanctuary of demons, and I proclaimed: 'The demons shall not be worshipped!' Where previously the demons were worshipped, there I worshipped Ahuramazda at the proper time and in the proper manner. And there was other business that had been done ill. That I made good. That which I did, all I did by the grace of Ahuramazda. Ahuramazda bore me aid until I completed the work.

Now on the face of this it does seem like an effort to institute Zoroastrianism as the state cult. But this would not square with the archaeological evidence from the empire (which makes it clear that most non-"proto-Zoroastrian" cult sites continued their activities unimpeded) and reading the inscription closely makes it clear that it is talking about only one of these many countries, and only one country which is in rebellion. Nor is it clearly an account of a historical revolt. It therefore makes more sense to read it as a sort of statement about the perogatives of the king towards rebellion; to the extent that all rebellion against the empire is the work of daivas, it follows that daivas inspire revolt and it is for that reason and that reason alone it is acceptable to suppress their worship. Incidentally, the eminent historian of the Achaemenid Empire Pierre Briant reads this as also limiting the religious authority of the Achaemenian King, proposing that it is as king of Persia and Persians alone that the King has direct authority over religious practices and not as king of Babylonia, or Egypt, or Lydia, or wherever else he should rule as king. Note that I am only addressing pre-Classical antiquity here; I cannot comment on the Classical world for lack of training as a classicist and discussing the state and religion in Late Antiquity entails dealing with a very different set of problems depending on whether or not we are talking about the Christian Roman Empire, the Zoroastrian Sassanian Empire, the or the early Islamic Caliphates.

EDIT: For further reading, I would recommend Mark Mazower's Salonica: City of Ghosts as containing some interesting discussion of Jewish communal leadership in Ottoman Salonica since it gives a good feel for how the religious leaders of a minority religion can gain more power over their followers when they are able to claim to be the official representatives of that religion's members. There is unfortunately no synthetic study of Hittite religion I am aware of, but the Society of Biblical Literature's Hittite Myth and Hittite Prayers provide a nice collection of Hittite primary sources that highlight the syncretic nature of Hittite religion. The most current monograph on Assyrian religious imperialism is Steven Holloways Assur is King! Assur is King!, but it is by no means a perfect book. The Babylonian policy of Sennacherib and Esharhaddon is discussed in Grant Frame's article "Babylonia: Assyria's Problem and Assyria's Prize"; my discussion of Esharhaddon's explanation of his father's Babylonian policy is also based on Esharhaddon's inscriptions, which are collected in The Royal Inscriptions of Esarhaddon, King of Assyria and translated by Erle Leichty.