Developer here - thanks for your kind words! There are several criteria to the matching algorithm that we use. Since battles run from 8am-8pm, we match people in the same time zone, with people who have been active recently, and with similar average step count. This makes it possible to not match people of completely dissimilar ability while still providing a diverse set of opponents.
