The criteria I would look for:
• A track record in guiding early stage products or services. The early days are as risky and ambiguous as it can get. Someone solidly aware of that going in is valuable.
• Multi-disciplinary. Highly probable that the first few employees will need to wear multiple hats and be able to shift between roles comfortably and as needed. It may not be coding, but ideally it is something tangible and measurable - e.g. the ability to PM a project or being comfortable enough to lead design/UX. Conversely, someone only willing to handle a single discipline - sales, fundraising, marketing, PR, etc. - will have limitations that become obvious right away.
• Domain expertise. May not necessarily have to be down to the exact problem domain but some level of familiarity helps in hitting the ground running.
• Comfortable as a distributed team. Since you brought up the location issue, it would probably help to have someone experienced in working virtually. Communication becomes even more crucial if you won't be interacting outside of a screen on a regular basis.
Where I would look:
• My network and extended network.
• The thankless, yet tried and true method of "pounding the pavement" and networking in person. Having "Terminator Vision" here using the above criteria is invaluable (there will be a LOT of noise to filter out).
• I'd consider looking around for past startups in a similar space that may not have worked out. Perhaps individuals from those teams still have that "itch."