The gemara in trying to figure out the p'shat in the mishna that prohibits sending meat from which the gid ha'nashe was removed to a goy, offers a few explanations. The final explanation is that it is a violation of geneivas da'as. Being that the first two answers are able to explain the mishna without inventing a concept of geneivas da'as, perhaps we shouldn't pasken like the approach that relies on this concept. The Rosh takes this approach and rejects the notion of geneivas da'as when one sends a gift to a goy, such as the case in the mishna and limits the problem of geneivas da'as specifically to a sale. With this he is able to work out the various other sources that indicate geneivas da'as is a real prohibition, but rejects applying the concept to the case of the mishna since it was being sent as a gift rather than a sale (עיין במעדני יו"ט ס' ר' שמוכיח מהש"ס שאין חילוק בין מכר למתנה). It would seem from the Rosh's approach that geneivas da'as applies to a sale but not a gift, that it is essentially an offshoot of the prohibition to steal. When one is giving a gift and not receiving anything in return as part of the compensation, it cannot be considered stealing. But, when one is receiving some level of compensation, it is prohibited to fool the buyer since the entire compensation is now being given under a false pretense (even though the buyer may have paid the same price even had he known the truth).
In my opinion there are 3 approaches to the nature of the issur of geneivas da'as. The Rosh holds that it is an offshoot of actual theft. Rashi and the Rambam reject the approach of the Rosh, yet differ in how they portray the issur.
Rashi writes multiple times in the sugya - ונמצא מחזיק לו טובה חנם. This implies that the prohibition is not stealing the compensation because rashi uses this logic even in the case of a gift where there is no compensation. Rather, the prohibition is not at the time of the geneivas da'as, it is violated afterward when you accept the goodwill of the receiver and his interest in responding in kind for something that he thinks you did for him, when in truth you didn't do for him as much as he thinks you did. It would seem from rashi that if one would notify the goy immediately after the violation of the geneivas da'as before he will have feelings of goodwill, he will avoid the entire prohibition. The issur is not in fooling the goy, nor is it in stealing compensation for the goy, but is is accepting his goodwill.
The Rambam in Hil. Dei'os 2:6 has what would be considered the simplest approach to the nature of geneivas da'as. The Rambam writes
אסור לאדם להנהיג עצמו בדברי חלקות ופיתוי, ולא יהיה אחד בפה ואחד בלב אלא תוכו כברו והענין שבלב הוא הדבר שבפה, ואסור לגנוב דעת הבריות ואפילו דעת הנכרי, כיצד לא ימכור לנכרי בשר נבילה במקום בשר שחוטה, ולא מנעל של מתה במקום מנעל של שחוטה וכו' ואפילו מלה אחת של פתוי ושל גניבת דעת אסור, אלא שפת אמת ורוח נכון ולב טהור מכל עמל והוות
The Rambam considers the prohibition to have nothing to do with the subject of the geneivas da'as. It is a violation of the מידת האמת that is expected of a Jew, and by lying to the anyone, even a goy, he is undermining this essential midah of being truthful. The difference between the Rambam and Rashi is that according to Rashi the prohibition exists because of the outcome of the undeserved goodwill that the Jew will receive from the goy, whereas according to the Rambam the issur is the act of deceiving another human being.