I can answer the first part of the question: Why are the underbraces choppy? The reason is that latex constructs the underbrace (also overbraces) from glyphs from a font (for the curly parts) and TeX rules (for the straight parts). The TeX rules translate into PDF filled rectangles, so you are correct that it is not a piece of type. Due to some tricky aspects of how the PDF format works, it's not really possible to ensure that these different parts meet seamlessly in all PDF viewers at all zoom levels.
Large vertical delimiters in TeX avoid this problem by using repeated glyphs also for the straight parts, so that the whole brace is constructed from only glyphs (there can be some slight glitches at the joins, but it is usually much less noticeable).
As for your second question: There are a few ways to deal with this, but none are really satisfactory.
- Use a different PDF viewer. Some of them use different drawing algorithms that make these glitches less obvious;
- Use different setting for your current PDF viewer. For example in Adobe reader go to the "Page Display" preferences page and under "Rendering" set "Smooth line art"=ON and "Enhance thin lines"=OFF. (This will have other effects that you may or may not appreciate);
Program a different way to generate horizontal braces, more similar to how vertical braces are constructed. Maybe take a look at how latex builds horizontal arrows, for inspiration. This is also how MnSymbol makes underbraces:

Use a font that provides large horizontal braces (I know you didn't want to change fonts, but...). For example the (commercial) MathTime Professional 2 fonts have individually designed glyphs for braces up to 4inches wide. For example (taken from this webpage):

- Don't worry about it: it will look absolutely fine when printed -- the problems with making the pieces match only apply to antialiased rendering at low resolution such as on a monitor (which PDF was not really designed for, originally). On the printed page (which PDF was designed for) they will match perfectly.
- Construct the braces using something like TikZ. I'm sure this is easy enough, but I'm not a TikZ expert so I'll let someone else write this.