Background/Objectives: Methicillin-resistant Staphylococcus aureus (MRSA) and methicillin-resistant Staphylococcus pseudintermedius (MRSP) represent important antimicrobial resistance threats related to companion animals, which can directly or indirectly lead to adverse health effects in humans and animals living in close contact. Characterizing the phenotypic resistance of MRSA and MRSP to a panel of antimicrobials relevant to both veterinary and human medicine is crucial within a “One Health” framework. Methods: In this study, a total of 79 presumptive MRSA isolates (34 from cats, 45 from dogs) and 110 presumptive MRSP isolates (105 from dogs, 5 from cats) from clinical cases were analysed. Real-time PCR was used to detect the presence of mecA and mecC genes, and susceptibility testing was performed using the Sensititre EUST2 panel. Results: Most of the isolates (88.9%, 168/189) were positive for the mecA gene, while a minority (1.1%, 2/189) were mecC-positive (2 MRSA, 1 dog, 1 cat). MRSP isolates exhibited acquired resistance to a broader range of antibiotics compared to MRSA strains. Furthermore, several isolates demonstrated acquired resistance to antibiotics considered critically important for human medicine. Resistance to vancomycin was found in an MRSP isolate from a dog, and resistance to linezolid in an MRSP isolate from a cat. This study reveals that 83.3% (30/36) of MRSA isolates from dogs and 89.3% (25/28) from cats were multidrug-resistant organisms, while MRSP isolates exhibited multidrug resistance in 99% (101/102) of cases for dogs and 100% (4/4) for cats. Conclusions: The extremely high level of multidrug resistance, with some isolates resistant to critically important antibiotics used in human medicine, highlight the importance of monitoring antimicrobial susceptibility in MRSA and MRSP isolates collected from cats and dogs in a One Health perspective.