In general I would recommend going with the coach who has real coaching experience, rather than the stronger player. Coaching and playing are not the same thing : the guy must be able to help you improve, rather than lecture you.
Specifically, I have worked with two coaches : Lazypawn (IM) and Artiom (IM).
The first is good if your level is strong enough (2000+) and keen on improving your opening play (he shares a lot of interesting ideas and analyzes). However, I stopped training with him, because he was using computers during analysis, and I'm more interested in (strong) human analysis.
Artiom is my current coach and his work is more thorough : he gives well-chosen thematic training positions during lessons and as homework, mostly on positional aspects of the game, (but I guess he could adapt this to your specific needs), and he has an efficient method of analyzing games, putting strong emphasis on critical points, post-game summary, and explanations of mistakes through a mix of positional and tactical considerations.
Take communication skills into account too : Skype is a must, decent English is a plus
At the end of the day, I would suggest to discuss the teaching method with the coach before purchasing lessons, and look for other pupils' experience.
PS : another criteria is the country of origin : I think coaches with a Russian background or from ex-USSR are probably better on average than Europeans, because they had the opportunity to work with better trainers themselves...