The recently started Arecibo L-band Feed Array (ALFA) pulsar survey aims to find ~1000 new pulsars. Due to its high time and frequency resolution the survey is especially sensitive to millisecond pulsars, which have the potential to test gravitational theories, detect gravitational waves and probe the neutron-star equation of state. Here we report the results of our preliminary analysis: in the first months we have discovered 21 new pulsars. One of these, PSR J1906+0746, is a young 144-ms pulsar in a highly relativistic 3.98-hr low-eccentricity orbit. The 2.61 +- 0.02 solar-mass system is expected to coalesce in ~300 Myr and contributes significantly to the computed cosmic inspiral rate of compact binary systems.