Large work well for size 10, so I would definitely recommend medium over small.
When I was putting the clip on my right pedal I saw the 'L' on the clip and stopped for a moment, "What? There is a difference between the left and right clips? Oh, that's 'L' for 'Large'..."
True story.