Just set the Apple TV to output the highest resolution that your TV can accept. If 720p is not an option, go for 1080i. Apple TV and most HDTVs can up- or down- convert the signals between any two formats. Some do it better than others, so you'll need to experiment, if you have the flexibility.
I have 3 HD sources for my 720p HDTV, and it really does not matter what the original programming is in,or what any of them output, the HDTV converts.