I have had pretty good luck using Detail Preserving Upscale effect that comes with AE. It is a little hard to find because it is in the Effects > Distort menu. I have even had some old VHS upscaled to HD come out pretty good.
Somewhat like you stated, it'll never look great. But depending on the source material, I have occasionally been amazed.
Well if you mean the best way vs an AE way, use hardware. Some of the Farrugia (sp?) boxes are spectacular. We have one here that puts out HD from SDI and the difference is indistinguishable (even flipping back and forth between sources)