We present the results of a large-area survey for millisecond pulsars (MSPs) at moderately high galactic latitudes with the 64 m Parkes radio telescope, along with follow-up timing and optical studies of the newly-discovered pulsars and several others. Major results include the first precise measurement of the mass of a fully recycled pulsar and measurement of orbital period decay in a double neutron star binary system allowing a test of general relativity along with improved measurements of the neutron star masses. In a survey of approx. 4,150 square degrees, we discovered 26 previously unknown pulsars, including 7 "recycled" millisecond or binary pulsars. Several of these recycled pulsars are particularly interesting: PSR J1528-3146 is in a circular orbit with a companion of at least 0.94 solar masses; it is a member of the recently recognized class of intermediate mass binary pulsar (IMBP) systems with massive white dwarf companions. We have detected optical counterparts for this and one other IMBP system; taken together with optical detections and non-detections of several similar systems, our results indicate that the characteristic age consistently overestimates the time since the end of mass accretion in these recycled systems. This result implies that the pulsar spin period at the end of the accretion phase is not dramatically shorter than the observed period as is generally assumed. PSR J1600-3053 is among the best high-precision timing pulsars known and should be very useful as part of an ensemble of pulsars used to detect very low frequency gravitational waves. PSR J1738+0333 has an optical counterpart which, although not yet well-studied, has already allowed a preliminary measurement of the system's mass ratio. The most significant discovery of this survey is PSR J1909-3744, a 2.95 ms pulsar in an extremely circular 1.5 d orbit with a low-mass white dwarf companion. Though this system is a fairly typical low-mass binary pulsar (LMBP) system, it has several exceptional qualities: an extremely narrow pulse profile and stable rotation have enabled the most precise long-term timing ever reported, and a nearly edge-on orbit gives rise to a strong Shapiro delay signature in the pulse timing data which has allowed the most precise measurement of the mass of a millisecond pulsar: 1.438 ± 0.024 solar masses. Our accurate parallax distance measurement, d = 1.14 +0.08 / -0.07 kpc, combined with the mass of the optically-detected companion, 0.2038 ± 0.022 solar masses, will provide an important calibration for white dwarf models relevant to other LMBP companions. We have measured the decay of the binary period of the double neutron star system B2127+11C in the globular cluster M15. This has allowed an improved measurement of the mass of the pulsar, 1.3584 ± 0.0097 solar masses, and companion, 1.3544 ± 0.0097 solar masses, as well as a test of general relativity at the 3% level. We find that the proper motions of this pulsar as well as B2127+11A and B2127+11B are consistent with each other and with one published measurement of the cluster proper motion. We have discovered three binary millisecond pulsars in the globular cluster M62 using the 100-m Green Bank Telescope (GBT). These pulsars are the first objects discovered with the GBT. We briefly describe a wide-bandwidth coherent dedispersion backend used for some of the high precision pulsar timing observations presented here.