In the Desert area of Route 111 (Which I assume is what you're talking about), these are the Pokemon that spawn
Sandshrew at level 19-21 with Poison Sting, Sand-Attack, Scratch, and Defense Curl
Trapinch at level 19-21 with Bite, Sand-Attack, and Faint Attack
Cacnea at level 20-22 with Pin Missile, Sand-Attack, Leech Seed, and Growth
Baltoy at level 19-21 with Self-Destruct, Rock Tomb, Psybeam, and Mud-Slap
In my opinion, Baltoy seems like the best thing you can get in the Desert
Baltoy learns a good Psychic STAB as well as an alright Rock move for coverage, and Self-Destruct as a fail-safe for when the Baltoy/Claydol is low on HP. Now, notice how I said Baltoy may be your best option in the desert, and not the best Psychic type in the game, as Claydol is outclassed by Grumpig and Kadabra, due to knowing Psybeam too once you catch a Spoink and Kadabra's fourth learned move through levelup being Psybeam, they're both also more attack orientated (As in, having better Sp. Atk and Speed), which is much better for a playthrough then defense is. Claydol also is weakened by its Ground type more then its benefited, as Mud-Slap is practically useless. Claydol isn't your WORST option though, as some of your other options are Medicham, which only gets Confusion, and Gardevoir which only knows Growl once you catch it. Claydol may be outclassed by other Psychic types too, but I've probably bored you enough.
You can also use Trapinch if you really want something with Dark type moves (which it can't really utilize well), and maybe Cacnea if you really want Pin Missile, but that's all there really is.
If you allow yourself to use Legendaries however, Regirock would be ludicrously helpful, and will likely carry you throughout the game.
Regirock learns Superpower, Ancient Power, Curse, and Rock Throw at the level you catch it at, giving you a great setup move as well as a good STAB and a great Fighting move. It'll will help you against Sidney, and also Glacia if you've got something to take care of her Water types for you know who. Regirock's problem is its speed, but its defensive stats let it take a couple hits to dish off enough damage to defeat the foe. All in all, Regirock seems like a team member worthy of a slot, as long as you're willing enough to get it, and have a place on the team for it.
I hope I've helped, and good luck on your challenge run!