This is an excellent question indeed!
Mainly yes, you can both accept and give gifts to non-Muslims. And there are many proofs for that from the Quran and Sunnah (some listed below).
Despite that, some scholars say that it's not permissible to accept gifts (but still permissible to give gifts) from non-Muslims, they have some proofs (listed in the source I provided at the bottom of the answer), but these proofs do not actually prove the prohibition. But there are some considerations on the exchange of gifts with non-Muslims, which are:
The gift should not be an interface for a bribe, bribe is utterly prohibited in Islam, it's prohibited to give and accept it from/to Muslims and non-Muslims alike.
The gift should not be helping to demonstrate the recipient's religion, like giving him a cross or a bible. Also it should not be a haram gift (this applies to Muslim-Muslim gifts too) such as giving him a bottle of wine or sexy songs... etc. This also includes that gifts shouldn't be given on religious holidays, because that might mean that you encourage and agree with them on their religion, and that's prohibited. However, as you noted in your question and Marc noted in his comment, Christmas is not celebrated in a religious way, it became only a good social interaction day. So this doesn't apply to this particular case.
It's recommended to make the gift leave a good impression for the recipient about Islam. In fact, one kind of the people that zakat is given to are new Muslims المؤلفة قلوبهم[Surat At-Tawbah:60], in order to make them love Islam more. In your case you can show how greatly respected parents are in Islam, you might like to try to demonstrate that through your gifts and interactions. Islam orders us to be devoted to our parents even if they aren't Muslims, moreover, even if they wanted us to become non-Muslims. As comes in [Surat Luqmān:15].
The gift should not be the result of or result in a bad thing. Such as making the non-Muslim recipient/receiver feel that he is better and his religion is the correct one. If you think he will, don't give or accept it. Another example is that it should not be over expensive, because wasting money is generally prohibited in Islam.
It should not be preferred to a more important thing, like helping a Muslim who is in need, priorities should be taken into consideration.
Some proofs that prove it's permissible to accept gifts from non-Muslims:
Some proofs that prove it's permissible to give gifts to non-Muslims:
لَّا يَنْهَاكُمُ اللَّهُ عَنِ الَّذِينَ لَمْ يُقَاتِلُوكُمْ فِي
الدِّينِ وَلَمْ يُخْرِجُوكُم مِّن دِيَارِكُمْ أَن تَبَرُّوهُمْ
وَتُقْسِطُوا إِلَيْهِمْ ۚ إِنَّ اللَّهَ يُحِبُّ الْمُقْسِطِينَ
Muhsin Khan Translation:
Allah does not forbid you to deal justly and kindly with those
who fought not against you on account of religion and did not drive
you out of your homes. Verily, Allah loves those who deal with equity.
[Surat Al-Mumtaĥanah:8]
Narrated Ibn Umar: Umar saw a silken cloak over a man for sale and
requested the Prophet to buy it in order to wear it on Fridays and
while meeting delegates. The Prophet said, "This is worn by the one
who will have no share in the Hereafter." Later on Allah's Apostle got
some silken cloaks similar to that one, and he sent one to Umar.
Umar said to the Prophet "How can I wear it, while you said about it
what you said?" The Prophet said, "I have not given it to you to wear,
but to sell or to give to someone else." So, `Umar sent it to his
brother at Mecca before he embraced Islam.
حَدَّثَنَا خَالِدُ بْنُ مَخْلَدٍ، حَدَّثَنَا سُلَيْمَانُ بْنُ بِلاَلٍ،
قَالَ حَدَّثَنِي عَبْدُ اللَّهِ بْنُ دِينَارٍ، عَنِ ابْنِ عُمَرَ ـ رضى
الله عنهما ـ قَالَ رَأَى عُمَرُ حُلَّةً عَلَى رَجُلٍ تُبَاعُ فَقَالَ
لِلنَّبِيِّ صلى الله عليه وسلم ابْتَعْ هَذِهِ الْحُلَّةَ تَلْبَسْهَا
يَوْمَ الْجُمُعَةِ وَإِذَا جَاءَكَ الْوَفْدُ. فَقَالَ " إِنَّمَا
يَلْبَسُ هَذَا مَنْ لاَ خَلاَقَ لَهُ فِي الآخِرَةِ ". فَأُتِيَ
رَسُولُ اللَّهِ صلى الله عليه وسلم مِنْهَا بِحُلَلٍ فَأَرْسَلَ إِلَى
عُمَرَ مِنْهَا بِحُلَّةٍ. فَقَالَ عُمَرُ كَيْفَ أَلْبَسُهَا وَقَدْ
قُلْتَ فِيهَا مَا قُلْتَ قَالَ " إِنِّي لَمْ أَكْسُكَهَا
لِتَلْبَسَهَا، تَبِيعُهَا أَوْ تَكْسُوهَا ". فَأَرْسَلَ بِهَا
عُمَرُ إِلَى أَخٍ لَهُ مِنْ أَهْلِ مَكَّةَ قَبْلَ أَنْ يُسْلِمَ.
[Sahih Bukhari]
Narrated Asma' bint Abu Bakr: My mother came to me during the lifetime
of Allah's Apostle and she was a pagan. I said to Allah's Apostle
(seeking his verdict), "My mother has come to me and she desires to
receive a reward from me, shall I keep good relations with her?" The
Prophet said, "Yes, keep good relation with her. "
حَدَّثَنَا عُبَيْدُ بْنُ إِسْمَاعِيلَ، حَدَّثَنَا أَبُو أُسَامَةَ،
عَنْ هِشَامٍ، عَنْ أَبِيهِ، عَنْ أَسْمَاءَ بِنْتِ أَبِي بَكْرٍ ـ رضى
الله عنهما ـ قَالَتْ قَدِمَتْ عَلَىَّ أُمِّي وَهْىَ مُشْرِكَةٌ، فِي
عَهْدِ رَسُولِ اللَّهِ صلى الله عليه وسلم، فَاسْتَفْتَيْتُ رَسُولَ
اللَّهِ صلى الله عليه وسلم قُلْتُ {إِنَّ أُمِّي قَدِمَتْ} وَهْىَ
رَاغِبَةٌ، أَفَأَصِلُ أُمِّي قَالَ " نَعَمْ صِلِي أُمَّكِ ".
[Sahih Bukhari], In fact this is very close to your case.
Source: this research paper about exchanging gifts and congratulations between Muslims and non-Muslims. By Dr.Ryadh Musaimiri, professor of the University of Al-Imam.
