This is a simple and a bit naive question. I understand that a miracle everywhere is a super natural force unexplainable by current state of science.
The Purim story looks all natural, nothing truly extraordinary.
I heard some refer to it as "hidden miracles", but I find it difficult to grasp, aren't those hidden miracles called "the nature"?
So what miracle(s) do we mean saying Nes Purim and Al Hanissim?
The "hidden miracle" of Purim is the power of the Passover. Let me explain.
The events in Esther occurred over the Passover. While Haman the Agagite relied on the timing of the divination of dice, or the purim, Esther had banked on the timing of Passover. In other words, the day that Haman hanged on the gallows was the turning point in the Exodus narrative, when the fate of the Egyptian army was cast (like purim, or dice) by Pharaoh, who decided to pursue the Jews. Remember, Esther delayed the disclosure of her petition to King Ahasuerus (Xerxes) by one day (until the 17th of Nisan), because this was the precise date for the turning point day in the Exodus narrative, when the fate of Pharaoh's army was "cast."
Please remember: Haman first announced the proclamation of the destruction of the Jews on the eve of the Day of Preparation, which is the 13th of Nisan (which is the eve of Passover).
Esther 3:12
12 Then the king’s scribes were summoned on the thirteenth day of the first month, and it was written just as Haman commanded to the king’s satraps, to the governors who were over each province and to the princes of each people, each province according to its script, each people according to its language, being written in the name of King Ahasuerus and sealed with the king’s signet ring. (emphasis added)
So the story starts on Passover! From this point in the narrative until the end of Chapter 7, the events in the Book of Esther span the Passover meal on the Jewish calendar (14-21 Nisan). That is, the Law of Moses had commanded the Passover meal and then the Feast of Unleavened Bread for seven days. However, Esther invoked a fast instead. The three days of Esther's fast are remarkable because they coincide with the Exodus of the Jews from Egypt. If this hypothesis is correct, then Esther may have chosen three days to fast because that was the time that Moses requested from Pharaoh as the time necessary needed to worship (Exod 5:3 and Exod 8:27). If this hypothesis is correct, the three days of fasting by Esther and the Jews was their worship time. The following graph depicts the Passover in relation to the decisive day when the fate of the Egyptians was cast (like purim or dice) three days after Passover.
Esther fasted during the 14-16 Nisan, and prepared her banquet for the king on the late afternoon of the 16 Nisan. (As noted, she and her fellow Jews would therefore not have eaten the Passover nor have partaken of the Feast of Unleavened Bread.) The late afternoon would mark the end of her fast for three days "night or day" according to Esther 4:16. At this very point in the Book of Esther (when she gives the first banquet) appears the following verse.
Esther 5:7 (NASB)
7 So Esther replied, “My petition and my request is [. . . .]
(ellipses added for emphasis)
In the Hebrew text, she does not finish the thought of the sentence. This verse is PIVOTAL (the turning point), because it occurs in the very center of the Book of Esther according to the endnotes of the Masoretic Text, which is found at the top of Page 932 of the PDF version online. This verse is in the very middle of the book, and so is the literary "hidden miracle" or TURNING POINT in the narrative. This verse is also the day that Esther breaks her fast, which occurs on the Festival of First Fruits, when a sheave offering was waived before the Lord in anticipation of his blessing to the Jews. Fifty from this date was when God gave the Law to the Jews at Sinai according to the Babylonian Talmud (Pesahim, Folio 68B). In other words, these very days portended very ominous spiritual power, but in the favor of the Jews. This was the apparent "script" followed by Esther.
If the foregoing paragraphs are correct, then Esther was following the "script" of the Exodus narrative. While there is no explicit mention of God (or even prayer) in the Book of Esther, it is very evident that Esther relied on the literal Torah (the Word of God as divine revelation) as her guide through the darkness of an imminent holocaust event. She met spiritual darkness with the divine power of the Word of God as typified in the Exodus narrative. In this regard, she postponed her petitions to King Ahasuerus (Xerxes), because the following day was the 17th of Nisan, which was the fateful (turning point) day when God had ordained the destruction of the army of Pharaoh, who was the enemy of the Jews. This is the logic of the apparent "script" followed by Esther. She did not know what tomorrow would portend, but she knew the "die would be cast" according to the Exodus "script": that is, the following day would somehow have to be the very day that God would ordain the destruction of arrogant Haman. And that is what happened.
The Book of Esther revolves around the timing of Passover and its significance as the "hidden miracle" for the demonstration of the power of God. This divine power destroys not only the enemies of the Jews, but also defeats the wicked spiritual powers behind them. Haman relied on dice (purim) to divine the most auspicious time to destroy the Jews, and implied here was divination, or reliance on outside wicked spiritual power. The Torah and Psalms are replete with references to defeating "the gods of the Egyptians" during the Exodus narrative (see Num 33:4 for example), and of course, as many, many scholars have observed, the ten plagues of Moses appeared to be in direct confrontation with Egyptian deities, or wicked spiritual powers.
In the same way, following the same "script," Esther's faith had demonstrated that complete reliance and trust in the Torah (Exodus narrative) was sufficient power to defeat the Jew's enemies and the wicked spiritual powers behind them. Prayer and God are never mentioned in any explicit terms in the Book of Esther, but the "script" of the Exodus narrative is very pronounced as the fate of Haman (and Pharaoh's army) was cast that fateful day of the 17th of Nisan, and that is the "hidden miracle" of Purim (the casting of fate).
The chassam soffer says ....
that the only miracle in the megilla that makes zero sense and is 100 percent miracle is the king going nuts and vashti going krazy and advisors saying kill her and he killing her
And there are some who say......
that the day of purim was by laws of מזלות, a bad day for jews and a good day for haman to wipe them out
so the fact that in the end on that day it became אשר ישלטו המה בשונאיהם is a huge nes of שידוד מזלות ומערכות because it was a total opposite
שיף דרשות (end of chullin )even adds it was a true כי בדבר זדונלה גר״א. מהרם שיף. מלבים. ועוד
In his introduction to Pirkei Avot, Rambam famously explains that all miracles are actually just pre-programmed into nature, so basically, they are all natural (or, more deeply, all of nature is a miracle). In Mishneh Torah, Yesodai Hatora 8:1, the Rambam strongly explains how a miracle is not meant to be there to enhance our belief in God.
So, in order to explain my answer, I have to disagree with your definition of "miracle" in the question.
The Torah idea of a miracle isn't the same as we understand the english word "miracle". The word is "Nes", which means "banner" or "sign". The connotation is that Hashem is raising a flag. When something happens, in nature, that points a finger to something Hashem wants us to see, that is a sign, a banner of His involvement, a נס.
As I heard from my Rav in shul this shabbat, the Maharal (חידושי אגדות - שבת כ״א:ד״ה כשנכנסו יוונים להיכל) talks about two types of נס. A Nes Nigle - an open miracle, and a Nes Nistar - a hidden miracle. This helps us understand something we say 3 or more times a day in davening: וְעַל נִסֶּֽיךָ שֶׁבְּכָל־יוֹם עִמָּֽנוּ. As the Rambam said, nature and miracles are one and the same, sometimes Hashem's signs are obvious, and they break the patterns of nature (perhaps even the law of nature, according to some opinions), and some, the vast majority, are hidden, and take the eye of emuna to see and appreciate.
If we continue this line of thought, Purim represented the beginning of the Jewish nation's full maturity, to escape the "miracle" system as part of our relationship with Hashem, and get a chance to engage in a relationship with Him without miracles, which is the ideal.
The avodah in this system is to see Hashem without the crux of miracles. The Purim story is told in this fashion. There are no "typical miracles" (clear breaks from the normal rules of nature), but that doesn't matter, you can still see that normal, routine nature is full of signs of Hashem. The story of Purim, read with the Oral Torah's commentaries, demonstrates this in many ways, which many of the answers here have already presented (and a great link collecting them is provided in the tl;dr). There are lots of things that "happen", that are seemingly happenstance, but when you are a person of emuna, and know that Hashem loves and protects His people, you put all these happenings together and are meant to come to the conclusion that Hashem was there, the Elokim, Master of Nature, watching over His people.
tl;dr: a miracle means a "sign" in lashon hakodesh. The Purim story is full of signs of Hashem and His will. They just happen to be non-miraculous (english word).
Additional thoughts/philosophisings
We aren't meant to view these miracles as signs that Hashem exists, according to Rambam. However, I would posit that we are supposed to view these miracles as signs that He still loves us and wants us, and our convenant with Him are eternal. Clearly, this is the "sign" that Hashem is giving at this critical part in our history.
All this was preparation for the future. The Chanuka oil marked the last obvious miracle, the last time Hashem held our hand before our big journey and mission into Galut, and ever since then, we have been plunged into a world of ceaselessly normal nature. As Jews, according to the Rambam, our job is to still see Hashem everywhere, in everything. Our job is to realise the true signs of Him, His love, and His greatness, which don't need no miracles to prove!
If illogical behavior can count as a miracle, the fact that Achashverosh made ground for building the Second Temple might count as such.
If we also assume that the building requires appointing a king and exterminating Amalek (see my question "do-the-3-mitzvos-of-entering-israel-apply-to-the-second-temple"), we could notice that Achashverosh inadvertently:
Raised the power of Mordechai (to a sort-of-king) and
Ruled to hang Haman and his followers and fight other Amalekites (sort-of-Mechiat Amolek)
and thus fulfilling the prerequisites for the Temple. As the interpreters picture him as initially hating the idea of letting the Jews build the Temple he unknowingly allowed it.
While the Megillah only says he finally taxed all the countries, it is probably after he realized his fault.
Hashem causing Achashverosh to change his mind when he didn't really want to, is a bigger nes than a mere change of nature.
Nature has no opinions or interests of its own. If Hashem wants it do something out of the ordinary it does it. No questions asked or opposition offered.
A person however has Bechira and a Yetzer Harah of his own. For Hashem to cause him to do something against his bechira is a bigger nes than nature doing what Hashem told it to do.
We, who are so used to people using their Bechira and an unchanging nature perceive a nes when we see the opposite of the latter and are clueless when the opposite of the former happens. That is why Purim is a hidden Nes
