The text of the relevant Gemara Avodah Zarah 3b:
אמר להם הקב"ה מכם יבאו ויעידו בהן בישראל שקיימו את התורה כולה יבא
נמרוד ויעיד באברהם שלא עבד עבודת כוכבים יבא לבן ויעיד ביעקב שלא נחשד
על הגזל תבא אשת פוטיפרע ותעיד ביוסף שלא נחשד על העבירה
Instead, the Holy One, Blessed be He, says to the nations: Let the
witnesses come from among you and testify that the Jewish people
fulfilled the Torah in its entirety. Let Nimrod come and testify about
Abraham that he did not engage in idol worship. Let Laban come and
testify about Jacob that he is not suspect with regard to robbery (see
Genesis 31:36–42). Let the wife of Potiphar come and testify about
Joseph that he is not suspect with regard to the sin of adultery (see
Genesis 39:7–12).
יבא נבוכד נצר ויעיד בחנניה מישאל ועזריה שלא השתחוו לצלם יבא דריוש
ויעיד בדניאל שלא ביטל את התפלה יבא בלדד השוחי וצופר הנעמתי ואליפז
התימני ואליהו בן ברכאל הבוזי ויעידו בהם בישראל שקיימו את כל התורה כולה
שנאמר (ישעיהו מג, ט) יתנו עידיהם ויצדקו
Let Nebuchadnezzar come and testify about Hananiah, Mishael, and
Azariah that they did not prostrate themselves before a graven image
It's basically saying that Hashem is saying that the nations of the world themselves can testify that the Jewish people kept the entire Torah. It's not at all implying that its premitted to bow down to a graven image; in fact, the very fact that Hashem is saying how "Let Nebuchadnezzar come and testify about Hananiah, Mishael, and Azariah that they did not prostrate themselves before a graven image", seems to prove that it is indeed prohibited to bow down to it according to the Torah. Now, what exactly is the scope of the prohibition? Comes along Tosafos:
שלא השתחוו לצלם - אומר ר"ת דצלם דנבוכדנצר לאו עבודת כוכבים הוא אלא
אנדרטי עשוי לכבוד המלך ובהכי ניחא דנקט גבי אברהם שלא עבד עבודת כוכבים
ובחנניה מישאל ועזריה שלא השתחוו לצלם וניחא נמי הא דאמרינן בפרק אלו
נערות (כתובות דף לג:) אלמלי נגדו לחנניה מישאל ועזריה פלחו לצלמא ואילו
היה עבודת כוכבים ממש חס ושלום כי מדאגת שום יסורין שבעולם לא היו
משתחוים לצלם כר' חנינא בן תרדיון (לקמן עבודה זרה יח.) ששמו ספוגין על
לבו ליסרו ור"ע (ברכות סא:) שסרקו בשרו במסרקות פיות והיינו הא דפריך פרק
מקום שנהגו (פסחים דף נג:) מה ראו חנניה מישאל ועזריה שמסרו עצמן לתוך
כבשן האש פירוש היה להם להשתחוות לצלם כיון שלא היה עבודת כוכבים ממש
ועוד ראיה מפ"ק דמגילה (דף יב.) מפני מה נתחייבו שונאיהם של ישראל כלייה
מפני שהשתחוו לצלם וכו' הם לא עשו אלא לפנים ואם היתה עבודת כוכבים היה
להם למסור עצמן על קידוש השם ולישנא דקרא נמי משמע הכי דכתיב לאלהיך לית
אנן פלחין ולצלמך לית אנן סגדין משמע דתרי מילי הוו:
So indeed Tosafos does say that there are two things, but he doesn't say that it's permitted to bow down to a statue, just that it's not "literally" avodas kochavim. Even though Tosafos says that "thye could have bowed to the statue since it wasn't literal Avodas Kochavim", but they had a reason not to, and it was still forbidden, like the Gemara that Tosafos himself brings before that proof (Pesachim 53b):
תא שמע עוד זו דרש תודוס איש רומי מה ראו חנניה מישאל ועזריה שמסרו
[עצמן] על קדושת השם לכבשן האש
Come and hear: This was also taught by Theodosius of Rome: What did
Hananiah, Mishael, and Azariah see that led them to deliver themselves
to the fiery furnace for sanctification of the name of God during the
rule of Nebuchadnezzar rather than worship idols under duress?
נשאו קל וחומר בעצמן מצפרדעים ומה צפרדעים שאין מצווין על קדושת השם כתיב
בהו ובאו [ועלו] בביתך [וגו׳] ובתנוריך ובמשארותיך אימתי משארות מצויות
אצל תנור הוי אומר בשעה שהתנור חם אנו שמצווין על קדושת השם על אחת כמה
וכמה
They drew an a fortiori inference on their own from the plague of
frogs in Egypt. With regard to frogs, which are not commanded
concerning the sanctification of the name of God, it is written: “And
the river shall swarm with frogs, which shall go up and come into your
house, and into your bedchamber, and onto your bed, and into the
houses of your servants, and upon your people, and into their ovens
and kneading bowls” (Exodus 7:28). When are kneading bowls found near
the oven? You must say that it is when the oven is hot. If in
fulfilling the command to harass the Egyptians, the frogs entered
burning ovens, all the more so, we, who are commanded concerning the
sanctification of the name of God, should deliver ourselves to be
killed in the fiery furnace for that purpose.
So true that even according to Rashi, the simple meaning, the statue wasn't an "Avodas Kochavim" mamash, let's look at Rashi:
מה ראו - שלא דרשו וחי בהן ולא שימות בהן:
So seemingly, it's not automatically included in the prohibited to give one's life over, as Tosafos there says, and goes according to his opinion in Avodah Zarah, he says in Pesachim (and he seems to say here that it's barely even a tecnical Mitvah Kalah, which one would be obligated to give ones life over in public):
מה ראו חנניה מישאל ועזריה - פ"ה מה ראו שלא דרשו וחי בהם ולא שימות בהן
וקשה דהא בפרהסיא הוה ומסקינן בסנהדרין (דף עד.) דלכולי עלמא בפרהסיא
חייב למסור עצמו אפילו אמצוה קלה ומפר"ת דצלם זה שעשה נבוכדנצר לאו ע"ז
הוה אלא אינדרטא שעשה לכבוד עצמו ולכך קאמר מה ראו וכן משמע מדכתיב לאלהך
לית אנחנא פלחין ולצלם דדהבא לא נסגוד משמע דאלהא דידיה וצלמא תרי מילי
נינהו ואתי נמי שפיר הא דאמרינן באלו נערות (כתובות לג:) אלמלי נגדו
לחנניה מישאל ועזריה פלחו לצלמא ואי ע"ז הוה ח"ו שהיו משתחוים לו ומיהו
לשון פלחו לא אתי שפיר ור"י מפרש מה ראו שלא ברחו שהרי קודם המעשה היו
יכולים לברוח כמו שעשה דניאל כדאמר בחלק ( סנהדרין צג.) ג' היו
but still the Gemara in Pesachim clearly says that even though we might not be tecnically commanded to not bow down to a "Tzelem" (which is why the Gemara asks the question of why did they do it), but we still have the kal vachomer from the frogs that nevertheless we still should give our lives for the sake of Hashem, so for sure in Mordechai's case, he had every right to not bow. It's not that they "should have bowed" since they were permitted to, Chas Veshalom; that's not what Tosafos is saying, he's simply answering a question: why does the Gemara ask why they should have done it, with which the Gemara itself answered, and especially according to the last opinion mentioned in the Tosafos in Pesachim...
But anyway, all of that was only regarding the incident of Nevuchadetzar, where Tosafos clearly says that it "only a statue made for the kings honor"; however, regarding Haman's idol, it seems that it was an Avodah Zarah according to all opinions, even though the Targum calls it a "אַנְדְרָטָא" (see later), and even besides the fact that maybe it could be debatable what the status of the statue of Haman was, it seems that Haman himself was considered an Avodah Zarah, it says in Ester Rabbah 7:8
מָה אָמַר לָהֶם מָרְדֳּכַי לְמִי שֶׁאוֹמֵר לוֹ: מַדּוּעַ אַתָּה עוֹבֵר
אֵת מִצְוַת הַמֶּלֶךְ, רַבִּי לֵוִי אָמַר, אָמַר לָהֶם מָרְדֳּכַי,
משֶׁה רַבֵּנוּ הִזְהִיר לָנוּ בַּתּוֹרָה (דברים כז, טו): אָרוּר
הָאִישׁ אֲשֶׁר יַעֲשֶׂה פֶסֶל וּמַסֵּכָה, וְרָשָׁע זֶה עוֹשֶׂה עַצְמוֹ
עֲבוֹדַת כּוֹכָבִים.
So according to this Haman made himself a literal "Avodas Kochavim" in addition to the statue around his neck, let's just quote the relevant Tosafos from Pesachim again:
דצלם זה שעשה נבוכדנצר לאו ע"ז
הוה אלא אינדרטא שעשה לכבוד עצמו
Now, let's look at the words of the Targum on Ester 3:4:
וַהֲוָה בְּמַלָלוּתְהוֹן לְוָתֵיהּ יוֹמָא וְיוֹמָא וְלָא קַבֵּל
מִנְהוֹן וְחַוִיאוּ לְהָמָן לְמֶחֱזֵי הֲיִתְקַיְמוּן פִּתְגָמֵי
מָרְדְכַי כָּל קֳבֵיל פִּתְגָמֵי דְהָמָן אֲרוּם חֲוֵי לְהוֹן דִי
לְהָמָן לָא הֲוָה סְגִיד עַל דַהֲוָה עַבְדֵיהּ דְאִזְדַבֵּן לֵיהּ
בְּטוּלְמַת לְחֵם וּלְאַנְדְרָטָא דִי הֵקִים בַּהֲדֵיהּ לָא הֲוָה
גָחִין עַל דַהֲוָה יְהוּדִי וִיהוּדָאֵי לָא פַּלְחִין וְלָא גָחַנִין
לֵיהּ:
He says that people told Haman that Morechai wouldn't bow to him because 1) Haman sold himself as a slave to Mordechai, and 2) because of the "אַנְדְרָטָא" that he had by him, and he wouldn't bow because "He's a Yehudi and Yehudim don't serve and don't bow to "it" (seemingly referring to the tzelem)"
Now, what exactly does "אַנְדְרָטָא" mean? Tosafos says that the "Tzelem" of Nevuchadnetzar was (only) a type of אַנְדְרָטָא that he made for his own honor, seemingly אַנְדְרָטָא just means "statue", I don't see any indication that the word אַנְדְרָטָא on its own implies something that's not Avodah arah; many Avodah Zarah's are statues. In fact, in the Jastrow dictionary, this word (in a different form) is simply translated as "statue":

Tosafos is just saying that Nevuchadnetzar's "image" wasn't an Avodah Zarah, it was just a "statue" that he made for his own honor, the stress isn't on the word "statue"; rather, on the point that it was only for his own honor, and it happened to be a statue, but that doesn't imply or mean that the word "statue" always excludes Avodah Zarah, especially since Haman would worship this "statue" as a literal Avodah Zarah according to the Midrash (see the end), and it seems pretty unlikely that the Targum would be arguing with this point of the Midrash... But basically, "statue" doesn't imply not Avodah Zarah, many Avodah Zarah's are, in fact, statues; the Avodah Zarah just means something that is worshipped as a "god", see Rambam hilchos Avodah Zarah (from the Gemara) where he says that even if people bow down to animals, plants or rocks (in some cases), they become Avodah Zarah with regard to certain laws.
So even if one might say that for some reason the word "אַנְדְרָטָא" does exclude Avodah Zarah, but certainly at least Haman himself was considered an Avodah Zarah since he made many people bow for him, and apparently consider him a god, like the Midrash Rabbah said above (that Mordechai told them the "he's making himself an Avodas Kochavim")...
And that itself is also another reason why the אַנְדְרָטָא of Haman should be considered an Avodah Zarah, not simply because it was a statue and all statues are not necessarily Avodah Zarah, but Haman wanted people to bow to the idol that he worshipped, and that itself gave it the status of Avodah Zarah, not the fact that it's a statue, but the fact that [he wanted that] people would worship it as a god (as the Targum himself says, that "...Yehudim don't worship it", implying that Haman wanted people to actually worship the "statue" as a god. In fact, let's look at the end of the Targum again:
וִיהוּדָאֵי לָא פַּלְחִין וְלָא גָחַנִין
לֵיהּ
"And Yehudim 1) don't worship and 2) don't bow down to it", it seems clear that according to the Targum, there are in fact 2 different things going on here, bowing down and worshipping it.).
so according to all opinions Mordechai was forbidden to bow to the Avodah Zarah "statue" that Haman (who was also an Avodah Zarah) had with him. And not only was this considered bonafide idol worship which anyone should rather be killed than transgress, and the Tosafos himself says that even if they would have tortured Chananyal Mishayel and Zecharya to worship a literal Avodah Zarah, they would have taken all the pain in the world; not only that, but it was in public, which Tosafos said in Pesachim that even a "Mitzvah Kalah", one is obligated to give ones life and not transgress.
Besides that, not only was he prohibited to bow down to it for his own sake, but even for the sake of the rest of the Jewish people [although I'm pretty sure that even for the sake of other people one is forbidden to transgress one of the 3 Mitzvos, and even a Mitvah Kalah in public, but perhaps there could have been a "Horas Sha'h", although I'm not so sure about that since I don't know if Mordechai had the authority to do so, but maybe it could be argued that for the sake of the entire Jewish people, it might be different (although I dont think there's any basis for that), but still:), he had good reason to like it says in Me'am Lo'az (I have one here right now) page 82 (at the end of verse 3:6) it says:
"Mordechai had an important reason for stubbornly refusing to bow,
even if it meant endangering the entire Jewish people. He knew that
the Jews had committed a terrible sin by bowing to Nebuchadnezzar's
statue. By his personal sacrifice, Mordechai was attempting to expiate
this sin"
SO maybe he though that through saving their sin, they would automatically be saved and there was nothing to worry about, since once they're forgiven (through his self sacrifice), then nothing could harm them.
Another point from me-am loa'z page 78, which shows how the "statue" Haman had was indeed an actual idol that he worshipped:
"Haman held the idol that he worshipped in his bosom as he
paraded through the town. He trusted in this idol, feeling that it
had helped him overcome Vashti and gain his present high position. He
held a representation of this idol, so that when people prostrated
themselves to him, they would also be kneeling to the idol [Yad HaMelech]."