The crucial issue is the speed of your router. Ideally you'd have the Apple TV connected to a router via an Ethernet cable using Gigabit Ethernet (1000/baseT) and your router would have WiFi N, not Wifi G (which is slower by a factor of about five), for the iPhone connection. Then you'd want to make sure that the WiFi N router was operating on a channel not subject to interference from other routers nearby, or from physical interference that would lead to signal attenuation.
It would be a good idea to try putting your WiFi router in the same room as your Apple TV and your iPhone and to see if video image quality improves. If so, this is an indication that you were experiencing WiFi signal attenuation due to interference caused by the materials used in the walls of the building.
Also, if this is the first time you've used an AppleTV, and the first time you've tried to watch HD video streaming over the Internet on your television, it may be that your Internet connection speed from your Internet service provider simply isn't fast enough to support HD video. If you have DSL, you may wish to consider upgrading to a cable modem or fiber-optic service with higher bandwidth. This year I found that AT&T had made their Uverse fiber-optic service available in my neighborhood. I upgraded to Uverse and got Internet service at four times the speed of my old AT&T DSL service for the same price I was paying for the slower DSL.