Polyelectrolyte-surfactant systems of opposite charge have been widely studied because of their relevance in applications ranging from pharmaceuticals to advanced materials. However, the role of hydrophobic interactions in such systems remains debated, particularly for sodium poly(styrenesulfonate) (NaPSS) and cationic surfactants. This study investigates the binding behavior of NaPSS with the conventional hydrocarbon surfactant dodecylpyridinium chloride (DPC) or the fluorinated surfactant 1H,1H,2H,2H-perfluorodecylpyridinium chloride (HFDePC), with the objective of elucidating the importance of hydrophobic interactions in such systems. The binding isotherms of both surfactants were measured in both linear NaPSS solutions and covalently cross-linked NaPSS hydrogels. HFDePC exhibited a binding isotherm with a negative slope, indicative of unique binding behavior. Thermodynamic modeling revealed that the negative slope arises from the formation of metastable colloidal states. For DPC, modeling indicated the formation of mixed micelles with NaPSS with a consistent surfactant/polyion charge ratio, explaining its lower cooperativity and atypical phase behavior. In NaPSS hydrogels, the swelling isotherms revealed a uniform hydrogel collapse in the case of DPC and the formation of biphasic core-shell structures in the case of HFDePC. Small-angle X-ray scattering showed rod-like micelle formation for both systems, with increased micelle length at higher binding ratios and the emergence of hexagonal packing of micelles near coil saturation. Overall, the findings of this study underscore the importance of surfactant and polyelectrolyte structure and hydrophobicity and offer new insights into the nature of interactions in polyelectrolyte-surfactant systems of opposite charge.