Great comment Lunar Xerneas, In addition I would suggest Adamant or Jolly because they lower special attack. Because Medicham is so frail, you don't really want to lower any defenses or speed. Adamant gives more power but less speed whereas Jolly has more speed but less power.
While poison jab is a great counter to fairy types (and grass which is covered by ice punch), however other possible moves could include fake out for support, or bullet punch which also hits fairys hard but also gives you priority but has less power.