Staphylococcus pseudintermedius is the predominant opportunistic pathogen in dogs causing primarily integumentary infections such as pyoderma and otitis. The worldwide emergence of methicillin-resistant S. pseudintermedius (MRSP) constitutes a significant health problem for companion animals in veterinary medicine. Thus, discovery of novel agents for treatment of MRSP-associated infections is highly warranted. In the present work, structure-activity relationships (based on testing of 37 peptidomimetics) have been explored with the aim of determining the influence of oligomer length as well as effect of fluorination, end-group modification, and length of hydrophobic side chains. Incorporation of fluorine atoms and elongation of hydrophobic side chains both conferred overall increased potency without significantly enhancing the hemolytic properties of the compounds. Importantly, it was found that when targeting MRSP, the peptidomimetic length could be reduced from 12 to 8 residues without substantial loss of antibacterial activity. By contrast, introduction of end-group modifications did not improve the activity against MRSP (10 strains tested), but conferred increased activity against Staphylococcus aureus, Escherichia coli, and Pseudomonas aeruginosa, albeit the concomitantly increased hemolytic properties resulted in a slightly lowered cell selectivity.