I don't think anyone was doing Rhyhorn (and it was still listed as undone) so I've done it.
Rhyhorn - Low Tier
Availability: Mid-game at the earliest. It is uncommonly found at levels 25-26 in the Safari Zone, and it is found in 2 of the 3 areas. There is a 15% chance of encountering one, so it is likely you will find a Rhyhorn somewhere. Their catch rate isn't too bad either, it can take a few attempts to get one. The only other place you can get one is in Cerulean Cave in Pokemon Yellow Version, but that's much later than practical.
Stats: Massive Attack and Defense make Rhyhorn/Rhydon an absolute powerhouse, and with a great HP stat it makes it a very strong pokemon. Unfortunately, it's low speed really hinders it and it's low special means that it should stay away from special moves.
Movepool: Rhyhorn has incredible TM capability, the kind most special sweepers would dream of, despite having a terrible special stat. As for level-up, Rhyhorn gets very little moves of any worth, and actually relies on TMs to give it STAB moves.
Power: Pure power best describes Rhydon, anything it hits, it KO's. It doesn't score many critical hits, but the raw damage output is always significant.
Type: Rock and Ground type are both great offensively, but defensively it's so-so. Immunity to Electric and resistance to Fire and Normal is great, but weakness to Grass (x4), Water (x4), Fighting (x2) and Ice (x2) is less than desirable.
Match-ups:
Erika: If you have Rhyhorn at this point (unlikely) then this is the last place to use it. Everything in this gym is faster and can cripple you with status or OHKO with STAB 4x Grass moves against your miserable Special stat. Leave Rhyhorn at home.
Koga: Rhyhorn wrecks if you gave it Dig or Earthquake, but if you didn't, it's very likely you will have normal-type moves. Rhyhorn still does ok in that case though, but watch out for poison.
Sabrina: Sabrina wrecks you here. Her pokemon are fast, high-powered and hit you in your pathetic Special stat. Even without weaknesses this is a bad match-up, although if you can survive a hit you can beat Kadabra as it's frail. But that's still a big IF.
Blaine: You come in with type advantage, but you won't like fighting here. Everything is faster than Rhyhorn, and even though he resists Fire, his special stat is atrocious. In addition, if Rhyhorn is burned, it will be pretty much useless. That being said, Rhydon should be able to take out Growlithe. The biggest threats come from Ponyta and Rapidash, who will both be faster than you and will trap you with Fire Spin. If you can move successfully however, you should take them out in 1 shot. Arcanine is a much bigger deal as you will be weakened by the time he arrives, and even though you resist Fire Blast, it can still KO you (or burn and cripple your attack stat).
Giovanni: This match-up very much depends on whether you taught Rhydon Earthquake/Dig, and only fight with Rhydon if he's level 51 to outspeed Giovanni's Rhydon, otherwise you risk Fissure. In this battle, Rhyhorn only knows crappy normal moves, Nidoking/Queen only have normal and poison moves and Rhydon can only hurt you with a lucky Fissure/Horn Drill. All of these Pokemon are hit supereffectively by Ground moves as well, but watch out for Dugtrio, because you won't like a STAB Dig (but is countered by your own Dig funnily enough).
Lorelei: Avoid avoid avoid. Lorlei can hit you with 4x Water moves and 2x Ice moves, and most of her Pokemon will be significantly faster than you. However, if you MUST fight her with Rhydon, make sure he knows Rock Slide to hit them back for 2x damage.
Bruno: Odd, but he actually does OK here. Both Onix are no trouble at all, and he can probably take down one Fighting-type Pokemon due to his high defense. However, Rhydon get's worn down very easily here, and won't solo unless he is extremely over-levelled.
Agatha: The sheer speed of her Pokemon plus Confusion/Sleep hax that her pokemon carry don't guarantee a quick or efficient sweep. If you can avoid these though (unlikely), then it's a clean sweep for Rhydon, as the best move each of them carry is essentially Night Shade.
Lance: If Rhydon ever picked a single moment to shine, it's here. Aside from Gyarados, Rhydon picks apart this team like it's no big deal. The only moves that any of them use are normal-type, and with Rhydon's massive defense and type resistance, it will be able to shake off the damage. It's worth noting though, Aerodactyl is still dangerous with Supersonic and immunity to Ground-type moves. In Yellow, Rhydon has a tougher time as his Dragonair has Ice Beam and Bubblebeam, while Dragonite now has Blizzard, but on the flip side, Aerodactyl no longer has supersonic, and the other Dragonair carries Thunderbolt (which you are immune to).
Rival: It doesn't matter what your Rival will be using here, he's going to have a different way of ending Rhydon in almost all circumstances. Charizard is the best starter to come up against due to it's weakness to Rock, but your terrible special means you will be eating Fire Blasts. Your Rhydon should be able to beat Pidgeot though, as it's frail. Exeggutor can be annoying with Hypnosis, but he only knows normal moves so he's no threat. Arcanine is easily beat, as Ember is piss-poor and his other moves just aren't up to scratch. The key Pokemon for Rhydon to completely avoid here is Blastoise, Venasaur, Alakazam and Gyarados who can all outspeed and OHKO.
Additional Notes: Rhydon would be awesome if it actually learned a single STAB move by level-up. And while it is able to beat regular trainers, it's useless in almost all of the important battles. It's unlikely that you saved Dig for Rhydon, and I would be hesitant to teach it Rock Slide and/or Earthquake. But, if you HAVE to use Rhydon, you need to give it these moves, it depends on them. Rhydon's TM movepool is amazing when it comes to special attacks, but unlike the Nidos, he doesn't have the stats to use them. In fact, Rhydon is a great special attacker in the same way Alakazam is a great physical wall. Rhydon does have a couple of interesting uses outside of battle, as it is able to use both Surf and Strength, so it's not a terrible HM slave. Overall, stick with Golem, Sandslash, Dugtrio, Nidoking or Nidoqueen, Rhyhorn is completely outclassed.
What do you guys think? Anything I need to add?