Optimizing the sensitivity of SQUID (superconducting quantum interference device)-relaxometry for detecting cell-targeted magnetic nanoparticles for in vivo diagnostics requires nanoparticles with a narrow particle size distribution to ensure that the Néel relaxation times fall within the measurement timescale (50 ms - 2 s, in this work). To determine the optimum particle size, single-core magnetite nanoparticles (with nominal average diameters 20, 25, 30, and 35 nm) were characterized by SQUID-relaxometry, transmission electron microscopy (TEM), SQUID-susceptometry, dynamic light scattering, and zeta potential analysis. The SQUID-relaxometry signal (detected magnetic moment/kg) from both the 25 nm and 30 nm particles was an improvement over previously-studied multi-core particles. However, the detected moments were an order of magnitude lower than predicted based on a simple model that takes into account the measured size distributions (but neglects dipolar interactions and polydispersity of the anisotropy energy density), indicating that improved control of several different nanoparticle properties (size, shape, coating thickness) will be required to achieve the highest detection sensitivity. Antibody conjugation and cell incubation experiments show that single-core particles enable a higher detected moment per cell, but also demonstrate the need for improved surface treatments to mitigate aggregation and improve specificity.