We use the density functional theory of statistical mechanics in a square gradient approximation to analyze the structure, size, and work of formation of critical nuclei in self-associating fluids where association reduces the strength of the interactions between bonded particles. This effect is expected in systems of strongly dipolar particles that associate into chains. In this work we analyze the nucleation behavior of two types of self-associating fluids: a system comprised of particles that can freely associate, and a system in which the association process involves a thermally activated initiation step. For the first case, we explore the properties of critical nuclei in fluids that exhibit a metastable critical point between a vapor phase and a highly associated liquid phase. In fluids where the association dynamics involves an initiation step, we investigate the nucleation behavior in the vicinity of the polymerization transition. In both cases critical nuclei undergo a structural transition that shares many of the features of the coil-globule transition reported in Monte Carlo simulations of strongly dipolar Stockmayer fluids. Our results suggest that the sharp structural transition observed in these simulations is evidence of the existence of a second-order or nearly second-order association transition in these model fluids.