There is substantial evidence for disk formation taking place during the early stages of star formation and for most stars being born in multiple systems; however, protostellar multiplicity and disk searches have been hampered by low resolution, sample bias, and variable sensitivity. We have conducted an unbiased, high-sensitivity Karl G. Jansky Very Large Array (VLA) survey toward all known protostars (n = 94) in the Perseus molecular cloud (d ∼ 230 pc), with a resolution of ∼ 15 AU (0.06′′) at λ = 8 mm. We have detected candidate protostellar disks toward 17 sources (with 12 of those in the Class 0 stage) and we have found substructure on < 50 AU scales for three Class 0 disk candidates, possibly evidence for disk fragmentation. We have discovered 16 new multiple systems (or new components) in this survey; the new systems have separations < 500 AU and 3 by < 30 AU. We also found a bi-modal distribution of separations, with peaks at ∼ 75 AU and ∼ 3000 AU, suggestive of formation through two distinct mechanisms: disk and turbulent fragmentation. The results from this survey demonstrate the necessity and utility of uniform, unbiased surveys of protostellar systems at millimeter and centimeter wavelengths.