I bought one of these for my home theater a while ago, and am VERY pleased with it:

DVDO iscan

With this, I upconvert everything to 1080i (it'll do 720P and other formats, too). I upconvert everything and use the component outputs to connect to my TV (DVI on my TV is problematic).

It's nice having this, because it automatically switches audio and video for me. Even my playstation2 is hooked up thru this and gets upconverted to 1080i and optical audio input. My DVD player also upconverts, but I've found that it looks better when I output 480P from my DVD, and have the DVDO upconvert to 1080i.