So, just in case it's not clear, your problem is that

TV can't play your .avi format. If you want them all to play using that

TV interface, they must all be converted to a format compatible with

TV.
iTunes is more flexible about this because it uses Quicktime as its base, so pretty much anything that plays in Quicktime will play in iTunes (including .avi files). You also have the horsepower in a laptop or desktop to handle dealing with various formats, and/or resolution and other video settings beyond what

TV's old and tired hardware can handle. For example, iTunes can play 1080i or 1080p HD video you might shoot with an HD camcorder, render in iMovie or FC, import into iTunes, and watch it there just fine. But that won't play via

TV, because the latter can only handle a relatively limited incarnation of 720p HD at best.
As someone else offered, you could set up a batch process (easy with visual hub) to convert your .avi files to .mp4 files friendly with

TV. But as you properly surmise, so many conversions will take a long time- even on fast hardware. And you'll lose some image quality going from one format to another.
Still, the UI is one of just a few remaining benefits that makes the

TV great (IMO), so if you want to use it to serve up your library on your TV, conversion is pretty much the only way to go.
If the old version of it's interface is good enough (front row), you could pick up a Mac Mini and use Front Row as your

TV interface. I've also seen reference to some kind of hack that can get the

TV interface running on a Mac Mini, but I don't know if that is true or not. Mac Mini's are pretty cheap on Ebay and similar, so that could be a way to go and save yourself all those conversions. I'm pretty sure Front Row is more flexible about what it can play (though I would test it with an .avi to be sure) before you go this way.