Over the past three decades a diverse collection of small protein domains have been used as scaffolds to generate general-purpose protein-binding reagents using a variety of protein display and enrichment technologies. To expand the repertoire of scaffolds and protein surfaces that might serve this purpose, we have explored the utility of (i) a pair of anti-parallel alpha-helices in a small highly disulfide-bonded 4-helix bundle, the CC4 domain from Reversion-inducing Cysteine-rich Protein with Kazal Motifs (RECK), and (ii) a concave beta-sheet surface and two adjacent loops in the human FN3 domain, the scaffold for the widely used monobody platform. Using M13 phage display and Next Generation Sequencing (NGS), we observe that, in both systems, libraries of ∼30 million variants contain binding proteins with affinities in the low uM range for baits corresponding to the extracellular domains of multiple mammalian proteins. CC4- and FN3-based binding proteins were fused to the N- and/or C-termini of Fc domains and used for immunostaining of transfected cells. Additionally, FN3-based binding proteins were inserted into VP1 of AAV to direct AAV infection to cells expressing a defined surface receptor. Finally, FN3-based binding proteins were insertion into the Pvc13 tail fiber protein of an extracellular contractile injection system particle to direct protein cargo delivery to cells expressing a defined surface receptor. These experiments support the utility of CC4 helices B and C and of FN3 beta-strands C, D, and F together with adjacent loops CD and FG as surfaces for engineering general-purpose protein-binding reagents.