This is definitely an issue with Premiere. It has several rendering quality settings that default to the LOWEST possible quality. The most important one is probably “Better Resizing” in the output options. Definitely check through the Premiere Project Settings and turn all “quality” settings up to maximum. Premiere should be able to give you good anti-aliased titles when all the settings are correct.
Also, if you are super-imposing the title over a background, the transparency mode is very important. Try “Alpha Channel,” “Black Alpha Matte,” and “White Alpha Matte” and pick the one that looks best.
At worst you could create the title in Photoshop as a 720x480 still image and them import it. (remember though that 720x480 pixels are not square, so create it at 640x480 then stretch it to 720 as a last step).