Enhancing interfacial interactions in fiber-reinforced polymer composites (FRPCs) is crucial for improving their mechanical properties. This can be achieved through the incorporation of nanomaterials or chemically functional agents into FRPCs. This study reports the tailoring of the fiber–matrix interface in FRPCs using non-functionalized graphene nanoplatelets (GNPs) in combination with a waterborne, highly branched, multi-functional polyurethane dispersion (HBPUD). A unique ultrasonic spray deposition technique was utilized to deposit aqueous mixtures of GNP/HBPUDs onto the surfaces of carbon fiber fabrics, which were used to prepare epoxy-prepreg sheets and corresponding FRPC laminates. The influence of the polyurethane (PU) and GNP content and their ratio at the fiber–matrix interface on the tensile properties of resulting high-performance composites was systematically investigated using stress–strain analysis of the produced FRPC plates and SEM analysis of their fractured surfaces. A synergistic stiffening and toughening effect was observed when as low as 20 to 30 mg of GNPs was deposited per square meter of each side of the carbon fiber fabrics in the presence of the multi-functional PU layer. This resulted in a significant improvement in the tensile strength from 908 to 1022 MPa, while maintaining or slightly improving the initial Young’s modulus from approximately 63 to 66 MPa.