You might be more satisfied with After Effects, but it's a bit more complicated. Premiere does have titling and some animation features but you can create much nicer stuff in AE.
For creating custom stuff you might use AE or even Photoshop. You could create lead lines or arrows and text in Photoshop, you can create mattes for custom transitions as well. After Effects is like Photoshop for animation.
The ideal setup would include all of the above, maybe even Illustrator..
As to why you would be disappointed with your output from Premiere, I can't say - not enough info in your post. It could be a pixel aspect ratio thing, or a compression thing. You can absolutely output perfect files from Premiere.
Maybe hit the Max forum, I'm sure there's info there on how to export from Max to work in HD in Premiere...
Autodesk 3ds Max
In the end, I'll say that Premiere is an editing and encoding app. If you need to create graphics to add to your 3D renders Premiere isn't the tool.
If you've been disappointed with titles in Premiere, try applying Gaussian Blur set to '0' to the title, it forces the effect to render on the underlying video before encoding.
Vince
