The gemara Avodah Zara (20) explains that praising a non-Jew is a violation of "lo sechaneim", and this is quoted in the Rambam (Hil. Avodah Zara 10:6) and the Shulchan Aruch (Y"D 151, and Shach s.k. 18 says that this applies to all non-Jews).
However, it seems like we aren't so careful about this. After all, Chazal themselves praised Antoninus and Dama ben Nesinah, and it seems like no one, from Rishonim (such as the Rambam's praises of Aristotle) to today, has any serious issue with this. Does anyone know of a source that discusses these specific cases or has a list of 'kulos' that would cover the common practice?
I know of a few exceptions (such the Shulchan Aruch there allows it if it's meant as a praise of Hashem or Jews) and the most widely applicable is probably that of R. Moshe Shterbach (Teshuvos Vehanhagos 4:197) who allows praising a non-Jew whom one doesn't know personally, but it seems like there must be more leniencies.