Rhydon:
Earthquake
Take Down
Megahorn
Thunderbolt
Starmie:
Protect
Psychic
Recover
Surf
Strategy: When you feel like using Earthquake, use Starmie's Protect the same turn you use it. This will not give Starmie any damage, and the Earthquake will attack both the enemies (unless they have "Levitate", or are Flying type). Thunderbolt is there for enemy Water types, which are one of Rhydon's weaknesses. Megahorn is the strongest Bug-type move, so use that against a Psychic or anything weak against Bugs. Take Down, because of Rhydon's Rock Head ability, in which negates any damage to Rhydon by self-damage-inflicting moves. Starmie's Surf and Psychic for STAB, and they are solid moves. Recover to heal any damage done to Starmie, and Protect is mostly there for Rhydon's Earthquake. Also, Earthquake the enemy if you think they are going to Dig; Earthquake deals double damage to any enemies using Dig.
Hope it helps.