We have undertaken a program of two searches at radio wavelengths for pulsars using the Arecibo Observatory. One search covered 70 square degrees of sky along the Galactic plane with sensitivity to pulsars with periods as short as 1 ms. The second search covered 170 square degrees between Galactic latitudes -50° and -30° with sensitivity to pulsars with periods of 0.5 ms or more. The sensitivity to long-period pulsars in both surveys was of order 1 mJy, with reduced sensitivity at the shortest periods. Twenty-five pulsars were detected between the two surveys. Ten of these had previously been discovered. Of the remaining fifteen new pulsars, thirteen are relatively young, slow pulsars, with periods between 0.212 s and 5.094 s. The latter period is the longest of any known radio pulsar; this pulsar also has an extraordinarily short duty cycle of 0.4%. Two millisecond pulsars were found. PSR J2019+2425 has a period of 3.934 ms and is at a distance of 1 kpc. It is in a 76.5-day binary orbit with a 0.3 M companion. Its orbital eccentricity is 1.1 x 10^-4. The spin-down rate of this pulsar is extremely small, and its evolutionary timescale of 9 x 10^9 yr is the longest of any known pulsar. Both the low eccentricity and the long evolutionary timescale put limits on violations of the strong equivalence principle which are competitive with the best previous limits. The second newly found millisecond pulsar, PSR J2322+2057, has a period of 4.808 ms and a distance of 0.8 kpc. It is the second isolated millisecond pulsar found outside of globular clusters. Its distance of nearly 0.5 kpc from the Galactic plane suggests that millisecond pulsars have a large scale height.