Is it okay at Christmastime to give a gift to a boss or for kids to give gifts to teachers if they are not Jewish?
I'm not so sure it's as straightforward as follick said. True that Christianity is avodah zarah for us Jews; true also that it is, according to some posekim, also the same for non-Jews. Nevertheless, one of the major leniencies in this regard (alluded to by Shalom in his answer to the related question) is that most non-Jews nowadays aren't אדוק באמונתם, so "frum" that, say, receiving a gift before their holiday will make them run to church to thank their deity.
There still is the issue of chukos hagoyim (imitating non-Jewish practices), though.
On a practical level: maybe indeed it's too late for this year to do anything about it, but how about if you give them an end-of-year present (or whatever you want to call it) far enough in advance - say anytime before Thanksgiving - so that it doesn't have a direct connection to Christmas, but still shows your regard for them?
I found something else that bears on this. The Rema (Yoreh De'ah 148:12), citing Terumas Hadeshen, says:
וכן אם שולח דורון לעובד כוכבים בזמן הזה ביום שיש להם סימן אם יגיע להם דורון בחג ההוא אם אפשר ישלח לו מבערב ואם לא ישלח לו בחג עצמו.
"Similarly, if one is sending a gift to a non-Jew in our times [by which, I guess, he means to distinguish them from the idol-worshippers of old], on the day on which they consider it significant to receive presents on that holiday: if possible, [the Jew] should send him the gift the evening before. If not, he may send it on the holiday itself."
(As Shach there :13 points out, delaying giving the gift until after the holiday would lead to איבה, the non-Jew resenting the Jew for having ignored the occasion. "Especially nowadays," he says, "when it is uncommon for them to go and thank [their deity, for the gift].")
However, in uncensored editions of Shulchan Aruch (such as here), the reference is explicated as being to "ביום ח' שאחר ניט"ל שקורין ני"א יאר" - "the eighth day after Christmas, which they call 'New Year.'" Which would mean that giving a non-Jew a gift on Christmas itself might still be problematic either as supporting idolatry or as chukos hagoyim, but if you give it as a New Year's gift, there'd be more room for leniency. (Why the posekim aren't as concerned about the chukos hagoyim angle regarding New Year's, I don't know.)
Though I suppose that it might be argued that conditions were different then - when the non-Jews' resentment could lead to real physical danger to the individual and to the Jewish community generally - than now.
No (Avodah Zara 2a) If Christianity is considered Avodah Zarah then it is clearly assur. I know that not everyone holds that it is but in cases of doubt about such a serious issur D'Orisah as Avodah Zarah we need to be machmir.