Solid rock would be fantastic, however the offensive Grass-Type Pokemon of RU would still be able to O/2HKO him most of the time. See:
252 SpA Life Orb Sceptile Leaf Storm vs. 88 HP / 84 SpD Eviolite Solid Rock Rhydon: 823-975 (220.64 - 261.39%) -- guaranteed OHKO
4 SpA Tangrowth Giga Drain vs. 88 HP / 84 SpD Eviolite Solid Rock Rhydon: 282-336 (75.6 - 90.08%) -- guaranteed 2HKO (Tank Tangrowth)
252+ SpA Choice Specs Tangrowth Leaf Storm vs. 88 HP / 84 SpD Eviolite Solid Rock Rhydon: 1074-1269 (287.93 - 340.21%) -- guaranteed OHKO (Offensive Tangrowth)
252 Atk Choice Band Skill Link Cinccino Bullet Seed (5 hits) vs. 88 HP / 0 Def Eviolite Solid Rock Rhydon: 285-345 (76.4 - 92.49%) -- guaranteed 2HKO
252 SpA Life Orb Swanna Surf vs. 88 HP / 84 SpD Eviolite Solid Rock Rhydon: 495-589 (132.7 - 157.9%) -- guaranteed OHKO
252+ Atk Guts Hariyama Cross Chop vs. 88 HP / 0 Def Eviolite Solid Rock Rhydon: 217-258 (58.17 - 69.16%) -- guaranteed 2HKO
252+ Atk Pure Power Medicham Hi Jump Kick vs. 88 HP / 0 Def Eviolite Solid Rock Rhydon: 243-288 (65.14 - 77.21%) -- guaranteed 2HKO
New spreads would have to be found for Rhydon to tank hits like these, but it would be very interesting and fun to use. Funnily enough I also thought up a Rhydon theorymon yesterday, I thought I posted it though...
What if Rhydon had Rapid Spin?
By spinning quickly, the user can escape from restraining moves.
This is the description of Rapid Spin. What does Rhydon do? Spin his horn. Quickly.
Obviously having a new defensive rapid-spinner would hurt Cryogonal and Sandslash a lot, while Kabutops could also see less usage from it. Those people who are willing to use Sandslash because of defensive rocks AND Rapid Spin will love Rhydon, while he can also go
offensive partnered with Trick Room. With Trick Room, Rhydon can beat Spiritomb 252+ Atk Rhydon Earthquake vs. 248 HP / 0 Def Spiritomb: 169-199 (55.77 - 65.67%) -- guaranteed 2HKO on the switch or simply keep him out. He could also run a Lum Berry and NOT use Trick Room support to beat out the ghosts. There would probably be a split for some time whether Rhydon or Kabutops was the better Rock-Type spinner, but the answer is that they go on different teams!
Also: 252+ Atk Choice Band Rhydon Rapid Spin vs. 64 HP / 0 Def Cryogonal: 89-105 (29.96 - 35.35%) -- guaranteed 3HKO after Stealth Rock
Muahahahahahaa!!