Nidoking doesn't learn Dig until next gen... Nor does Stantler by the way (nor does his learn it ever in the later gens). Mud-Slap is too weak to take seriously, and Earthquake is heavily competed for.
What's the difference between GS Nido and C Nido? Aside from Crystal's move tutor, the Tohjo Falls Moon Stone is available in all three versions. It's not one of the stones you need a phone call for.
Also, I followed Colonel M's lead and took a look just how big the stat / type attack boosts are in this game as a result of getting different badges. Here are my discoveries until Kanto:
Assuming a Chuck -> Jasmine -> Pryce route for easier navigation with the Fly HM. You get a 9/8 boost to attack after Falkner, and a 9/8 boost to special attack after Pryce, plus you get a 9/8 boost for each type whose badge you possess, so phys attackers are at an advantage for a while. Also note that a lot of elemental types are not represented in Johto at all, and that the first 6 gyms are all physical.
This basically shows why normal-types using their STABs hurt as much as they do - besides good availability of moves (and really strong users thereof, like Tauros, Miltank, Stantler, Ursaring) and high-powered early Returns being there, you also get roughly a 26% bonus to attacks which is like half a STAB - hence using normal moves almost feels you're using super-effective coverage when done by STAB-users... Except the coverage is extended to everyone that's not a rock or steel type. This explains why Tauros and co. are as good as they appear to be.
Just something to look at and consider in the future; not sure if I should try to get Spearow into A tier by appealing to how early the 26% boosts to its STABs come, but it could help its case if we do investigate into that particular mon.