There's an extensive walkthrough over at Gizmodo covering how to use Handbrake for downsampling your 1080i/p videos to a more manageable resolution, very helpful if you're in a DIY mood -- but there is an easier way. It takes advantage of a feature in an app you're already using: iTunes.
Just select your movie file(s) and check under the Advanced menu. See those two "Create..." options? The iPod or iPhone version will deliver a resampled video at a resolution the smaller devices can manage; the iPad/Apple TV choice will spit out a 720p file. All you need to do is select your choice and wait for a while... depending on the length of your video and the speed of your Mac, it may take quite a long time, but be patient. You can try out the steps with an Apple-provided sample file, if you like.
Once the conversion is done, you'll see a second instance of the video in your media list -- then you can sync at will. Note that if the file you're choosing is already adequately low-res, you'll see the dialog box below.