1) This is an argument among the Rishonim, with most seemingly siding that this is an Isur mid'Oraisa.

2) Here, as well, there is an argument among the Rishonim, with some Rishonim stating Geneivas Da'as in general is mid'Rabanan. It is hard to say that one is more stringent than the other, as one should treat Geneivas Da'as as an Issur mid'Oraisa by a non-jew as well. However, in cases of Geneivas Da'as which do not involve business, Geneivas Da'as is certainly more lenient than Gezel Akum.

3) Here are some of the various opinions. The Shach (C.M. 348:1) quotes the Rambam, Tur, Shulchan Aruch as saying that stealing from a non-jew is and Issur mid'Oraisa. Rashi in Sanhedrin (57a, DH "Yisrael") holds it is mid'Rabanan. The Ritva in Chulin (94a) and the Smag (Lavin #155) understand that Geneivas Da'as is an Issur mid'Oraisa by a non-jew as well. The Smak (#261) understands that the prohibition of Geneivas Da'as in general (even by a Jew) is mid'Rabanan. There is an argument among the Rishonim regarding whether or not the prohibition applies to a non-jew when no business is involved (see for example Tosfos in Chulin 94a, DH "Amar" and Ramban and Rashba in Chulin 94ab).

All the best,

Yaakov Montrose