Let's get the obvious out of the way: This is a fucking desert region, so let's focus on the ground types:
https://bulbapedia.bulbagarden.net/wiki/Ground_(type)There are plenty of pokemon that would fit the bill, but remember, the player would focus on only leveling up one or two, so no need for several pokemon that all do the same thing
Good Candidates: Sandshrew, Diglett(Caves), Phanpy, Trapinch(In sandstorms/bottom of sand dunes), Hippopotas, Drillbur(In Caves)
Rhyhorn, sandile, numel, larvitar, onix and gligar are good choices as well. Baltoy could also be found around agate, since the town has some supposed "Magic Power" Surrounding it or some crap. Sandyghast could be found in the beaches/oasis areas
