The priority, of course, is to teach the body and the mind some aspects of the way of the warrior.
Because everything has to do with the handling of the body, the nerves and the mind in physical discomfort and tense situation, any art will do as long as the teacher is a moral person (to avoid excessive injury), there's a healthy dose of athletic challenge (to counteract escapism, desire for comfort and fat ass) and of course one's own attitude.
Based on modest experience, I recommend the extremely difficult Judo, one of the operative Jujutsu schools or the eclectic Bujinkan Budo Taijutsu.