I think if I was describing someone, I'd be more likely to talk about height and build:
He was of average build / His build was average
He was of average height / His height was average
and I'd probably use 'average' instead of 'medium'. The problem if you said 'medium sized' is that I wouldn't be completely clear whether you were talking about the person's build or height. I don't think, if I was talking to the police and describing two bank robbers, one 1.85m and the other 1.55m tall and both with an average build, I'd say: 'They were both medium sized.'
However, the jacket wrestled off the back one of the robbers as he struggled to flee the scene might be medium-sized, their getaway car might be a medium-sized saloon and they might have been spotted each eating a medium-sized burger and fries at McDonald's a couple of hours after the robbery.
