Airplay is a lossy process and must compress the display frame on the sending device in real time and transfer the compressed image to the AppleTV - it will adapt and give worse results with slower LAN speeds.
Bear in mind that if both the AppleTV and sending device are wireless they have to share available LAN bandwidth, whereas AppleTV playing from the internet may be the only active wifi connection.
So yes in theory having AppleTV on ethernet may well help.
It may not be the whole issue though. You may be seeing a difference between your plasma and LCD TVs - I've always preferred the smooth look of plasmas whereas LCD these days tends to give razor sharp pics that could accentuate any pixellation artefcat by just looking sharper. Are the TVs located in different areas, as if in same place the wifi characteristics for Airplay would be the same for both in theory (unless new TV causing interference and degrading wifi speed - maybe reposition AppleTV?).
Also some TVs have aggressive motion compensation features that whilst sounding good in theory can actually make some content look worse - have a play with your TV set settings.
I have a similar issue. Using a wired connection on my appleTV did not solve the problem.
I figured the issue was slow LAN, but I'm not convinced anymore. I have my appleTV wired now, with my router 10ft from my iMac which is connected using a 5GHz wireless connection. Even with no traffic on my LAN, I see the same problem