I'd think that you'd do best with a coach that has real coaching experience, other things being equal.

I'd also suggest trying both. When looking for an online coach I had lessons with a few different people.

A couple of points:
 
1) The difference in rating between the players may not be at all relevant, although it depends a bit on your own level. It might feel nice to have a stronger coach but if one guy is 400 points higher than you and another 500, it's unlikely that you'd be able to tell the difference in their playing strength. In both cases they'd be significantly stronger in all aspects of the game and have plenty to teach you.

2) I think it's more relevant to see what sort of chess style your potential coach has. What sort of influence do you want on your own style? I'm an intuitive positional player. I've found it helpful to have a coach with a more dynamic style, who could point out a lot of possibilities in my games I'd never have considered and weren't necessarily the top choice of the engine. Over time this has resulted in me seeing and playing more of those things during my games. On the other hand, maybe you want a coach who plays in a similar style to you, who can help you hone those skills.

Take some lessons from both of them and decide then.