Carbon nanoparticle coatings on laser-patterned stainless-steel surfaces present a solid lubrication system where the pattern’s recessions act as lubricant-retaining reservoirs. This study investigates the influence of the structural depth of line patterns coated with multi-walled carbon nanotubes (CNTs) and carbon onions (COs) on their respective potential to reduce friction and wear. Direct laser interference patterning (DLIP) with a pulse duration of 12 ps is used to create line patterns with three different structural depths at a periodicity of 3.5 µm on AISI 304 steel platelets. Subsequently, electrophoretic deposition (EPD) is applied to form homogeneous carbon nanoparticle coatings on the patterned platelets. Tribological ball-on-disc experiments are conducted on the as-described surfaces with an alumina counter body at a load of 100 mN. The results show that the shallower the coated structure, the lower its coefficient of friction (COF), regardless of the particle type. Thereby, with a minimum of just below 0.20, CNTs reach lower COF values than COs over most of the testing period. The resulting wear tracks are characterized by scanning electron microscopy, transmission electron microscopy, and energy-dispersive X-ray spectroscopy. During friction testing, the CNTs remain in contact, and the immediate proximity, whereas the CO coating is largely removed. Regardless of structural depth, no oxidation occurs on CNT-coated surfaces, whereas minor oxidation is detected on CO-coated wear tracks.