Biofilm formation is a key mechanism of antimicrobial resistance. We have recently reported two classes of orally bioavailable C-glycosidic inhibitors of the Pseudomonas aeruginosa lectin LecB with antibiofilm activity. They proved efficient in target binding, were metabolically stable, nontoxic, selective, and potent in inhibiting formation of bacterial biofilm. Here, we designed and synthesized six new carboxamides and 24 new sulfonamides for a detailed structure-activity relationship for two clinically representative LecB variants. Sulfonamides generally showed higher inhibition compared to carboxamides, which was rationalized based on crystal structure analyses. Substitutions at the thiophenesulfonamide increased binding through extensive contacts with a lipophilic protein patch. These metabolically stable compounds showed a further increase in potency toward the target and in biofilm inhibition assays. In general, we established the structure-activity relationship for these promising antibiofilm agents and showed that modification of the sulfonamide residue bears future optimization potential.