Mediums are definitely better than large. But if you are sure it is a male and not a female I would try to go back to smalls, they say offering larger prey can lead to refusals. I agree with moose if you continue to offer mediums every 2 weeks be soon enough. But I think in the long run you would be better to offer smalls every 7 to 10 days. Can you post a pic so we can get a idea how urgent your snake needs to eat?
PS Just noticed where you said in the future you would maybe get smalls, I think that will work better for you.