My understanding from Sanhedrin 82a is that there is no halachic construct of marriage by non-Jews and as such Potifar(a)'s "wife" should not have been forbidden to Yosef. It was only later during the times of the Chashmonaim that a decree was made against this type of adultery. Why then does Yosef say it would be a sin to God (Bereshis 39:9)?
Yes, there is an issue of mitsvat asse in bne noach from which we can say that it have been a sin. See Talmud Bavli Kiddushin 21b:
וראית בשביה ת"ר וראית בשביה בשעת שביה אשת ואפילו אשת איש
Our Rabbis taught: 'And thou seest among the captives' - when taking her captive; a woman - even married.
See Tosfot there
אשת אפילו אשת איש. ואע"פ דאין אישות בכותית כדאיתא פ' ד' מיתות (סנהדרין נב:) מ"מ איכא עשה דכתיב (בראשית ב) ודבק באשתו ולא באשת חבירו.:
Tosfot explains that despite that in Sanhedrin gemara says that there is no marrital status among bene Noach, there is a prohibition, derivated from a positive mitsva. The mitsva is "Therefore shall a man l....... , and shall cleave to his wife"
So the gemara in Kiddushin taugh that the special situation of yefat toar, can counter this prohibition. Without this mitsva, it remains a sin.
There's another side of a coin. Here's some reasons why it was not / could not be / could be not a sin:
"Sin" is a matter of different perspectives. Remember Moses shattering the Luchot? Was it a sin? From our Halakhic perspective it was surely a sin of "לא תעשון כן לה"א" - a branch of idolatry (we're forbidden to loose Divrey Kodesh). But for Moses - it was a great merit (some other times he, however, greatly "failed"). So the situation with Yossef could turn out either way - either Hashem was praising Yossef for this idea, or scolding him - about 50% chance.
Before Matan Torah, the "self-emerged" Jews enjoyed a special status: they left the status of gentiles and did not yet reach the status of full Jews (hence the dispute on their status in Gemorah). This situation allowed them to be technically exempt from obeying the Mitzvot, as those were yet given in verbal and explicit form. So Yosef being a Jew was Potur of having relations with a married gentile woman, and he was yet to be commanded all the late prohibitions, like "haBoel Aramis", "Le Titchatnu", etc.
We hold Yosef to be a Tzadik not only in his deeds, but his intentions also. However (according to Shmuel), he had clear intentions to have sex with this woman as he saw in prophecy the two tribes (of his sons) coming from her descendants. If so I can conclude two possible explanations: either he didn't hold it to be a sin (as we wouldn't expect him to readily sin), or he had a better Mitzvah to do (see Yaakov with the two sisters, Yosef not honoring Yaakov for years etc).