Caterpie belongs in bottom tier in my opinion, All it has is Psybeam and a Sleep Move. Poor stats as well. Just a sleep move doesn't warrant it being moved up in my opinion. Raising it just seems like wasting exp points (along with EVs).About choosing Nidoran (f) over Nidoran (m): In LeafGreen NidF is a lot more common than NidM. And I mean a lot.
Also I'm for Sandshrew to High Tier. In this game Ground types are amazing, especially against all those Poison lot (Team Rocket and Koga). STAB Dig and later Earthquake is great, so is Slash.
Caterpie to Low. Sure it's weak Later game but Early - Mid game it's great, with the nearly 100% accurate Sleep Powder and Psybeam doing decent damage. I used it in the E4 and although not as powerful as the rest of the team, it did it's job: statusing.
At least Low.
And Sandshrew for high sounds fine. Can get it early in the game and like you said helps you beat all of team rockets lol Poison-types.