If he's scared of dancing for social reasons, I would think that the underlying causes of that would have to be addressed. Off the top of my head, this might be a good gradual behavioral approach (but wouldn't address any of the underlying cognitive causes):

1. Pen pal.
2. Do something that involves cooperation in person, but not socializing.
3. Go to a meetup that is like semi-professional and semi-social.
4. Go to a social meetup.
5. Toastmasters.
6. Learn to dance.
7. Initiate small talk in acceptable situations (with the barber, taxi driver, contextual comments to the person sitting next to you).
8. Initiate in a more random way. Ex. Hey, I like your glasses, where'd you get them? Something tells me that you're a <sport> fan - did you see the <home team> game last night?

If his fear is more specific to physical activity, then I agree with you about starting off with something like Yoga. Some other ideas: Racquetball, Running, Ping Pong.