After renting a place from a non-Jew, I realized I left with a small object accidentally. Am I obligated to return it as a "stolen" object, or is it considered a "lost" object that I am not obligated (and possibly forbidden) to return?
One classical halachic case is one of accidentally switching items (from here)
One who [accidentally] took the wrong item while at the house of a mourner or while participating in a festive meal, may not use the item [that he accidentally took] and doing so is considered stealing.
Regarding the object being possibly forbidden to be returned to non-Jews, it is true the concern exists in some cases (see sources here) but note the Rambam (Gezelah va'Avedah 11:3) who writes (regarding a found object, not something you took by mistake)
if one returns to sanctify God's name, so that others will praise the Jewish people and know that they are trustworthy, this is praiseworthy.
The Rambam's language regarding stealing from a gentile is much stronger (Gezelah va'Avedah 1:2)
It is forbidden to rob even the slightest amount. It is forbidden even to rob or to withhold money from a gentile who worships idols. If one robs or withholds money from such a person, one must return it.
Regarding the combination of stealing by accident (which is addressed in halacha) and doing so from a non-Jew (which is not - the classical case is whether to return a lost object), I would argue that no one would think it is OK to take things accidentally from non-Jews and not return them. And argue that, if the Rambam writes one should return a lost object if it is a kiddush Hashem, it is an even stronger recommendation if one accidentally took something from them!
Therefore I believe that, in the spirit of Dvarim 6:18 "Do what is right and good in the sight of the Lord", the right thing to do would be to call the person and ask
- whether he/she wants the object back? or
- whether you can reimburse him/her for it? or
- whether the object is insignificant to him/her?
See also the story of Shimon ben Shetach from Yerushalmi Bava Metzia 2:5, as well as here from R Daniel Mann ("of course, he has to return it when he finds out the truth"), here regarding the definition of an akum vs. today's non-Jews, here for further halachic sources and here.