No big, it just means we need a dedicated counter to prevent a counter-sweep by Medicham (arguably the only threatening thing that can beat a set-up Rhydon that we lose to with Adamant), since we might not be able to guarantee Rotom being alive in the mid/late-game.
Offensive partners:
Scyther (speed+coverage, CB would work nicely to throw out U-turns)
Rampardos (niche coverage to beat specific walls, general stallbreaking power without SD)
Bouffalant (defensive switch into almost all grass types if Rhydon is forced to SD instead of RP, can tank an unboosted hit and respond, good switch-in for Tangrowth and has Megahorn for the bulky psychics Claydol and Uxie)
SunnyBeam Entei (don't laugh this one out. Sets up weather, fries bulky waters with SolarBeam, fries physical walls with boosted Fire Blast, can carry Stone Edge for other Entei and will outspeed standard variants by being able to run a +Spe nature)
SubRoost Krow (can muscle through Tangrowth/Gallade and have priority to handle scarfed threats, Moxie allows it to be a backup physical sweeper if Rhydon fails to do the job)
Rotom-N (covers Medicham, BU Gallade, and spinblocks to keep hazards up while being offensive, can also run Volt Switch and SubSplit)
Defensive partners:
Qwilfish (nasty shared ground weakness and only neutral to grass but is an extremely bulky spiker, also has tspikes and twave and priority)
Roselia (spiker that has better type synergy but folds to physical attacks, is also a good switch-in opportunity for Entei/Typhlosion/Zard)
Mismagius (bulky spinblock, can spread residual damage and perhaps perish trap a troublesome wall)
Drifblim (again, don't laugh this one off. spinblock, then sub+stockpile and pass to Rhydon who can then accumulate multiple boosts with the extra provided bulk or the free turn provided by Substitute)
Slowking (can provide twave support, sponge special attacks, and cover ferroseed/tangrowth with fire blast)
Just my first ideas. Good cases can be made for a LOT of pokemon here. I bolded the ones that I think might be particularly useful, but yeah...
Offensive partners:
Scyther (speed+coverage, CB would work nicely to throw out U-turns)
Rampardos (niche coverage to beat specific walls, general stallbreaking power without SD)
Bouffalant (defensive switch into almost all grass types if Rhydon is forced to SD instead of RP, can tank an unboosted hit and respond, good switch-in for Tangrowth and has Megahorn for the bulky psychics Claydol and Uxie)
SunnyBeam Entei (don't laugh this one out. Sets up weather, fries bulky waters with SolarBeam, fries physical walls with boosted Fire Blast, can carry Stone Edge for other Entei and will outspeed standard variants by being able to run a +Spe nature)
SubRoost Krow (can muscle through Tangrowth/Gallade and have priority to handle scarfed threats, Moxie allows it to be a backup physical sweeper if Rhydon fails to do the job)
Rotom-N (covers Medicham, BU Gallade, and spinblocks to keep hazards up while being offensive, can also run Volt Switch and SubSplit)
Defensive partners:
Qwilfish (nasty shared ground weakness and only neutral to grass but is an extremely bulky spiker, also has tspikes and twave and priority)
Roselia (spiker that has better type synergy but folds to physical attacks, is also a good switch-in opportunity for Entei/Typhlosion/Zard)
Mismagius (bulky spinblock, can spread residual damage and perhaps perish trap a troublesome wall)
Drifblim (again, don't laugh this one off. spinblock, then sub+stockpile and pass to Rhydon who can then accumulate multiple boosts with the extra provided bulk or the free turn provided by Substitute)
Slowking (can provide twave support, sponge special attacks, and cover ferroseed/tangrowth with fire blast)
Just my first ideas. Good cases can be made for a LOT of pokemon here. I bolded the ones that I think might be particularly useful, but yeah...