Starmie definitely deserves High tier, in my opinion. You get it late, but it is useful in nearly every scenario following its capture.
-If you skip Winona to get it, you have Thunderbolt/Ice Beam to use on it, and you aren't using the latter on anything else if Starmie is your Water-type. Surf alone will kill Tate and Liza since Starmie resists Psychic, and its Thunderbolt will defeat most of Wallace/Juan's team since it resists Water. Natural Cure even helps it out against Toxic, if you need multiple Thunderbolts to win. When it comes to the E4, it sweeps the last two and fares at least decently against the Champion, faring better against Steven than Wallace, IMO. Surf / Ice Beam / Thunderbolt (Or Thunder, even) / Recover will clean up real easily.
I also think Treecko is getting an unnecessarily bad rap. It is one of those good at the start, average mid, gets better at the end type of pokemon that shouldn't be overlooked. Here's my reasoning, assuming Leaf Blade / Dragon Claw / Aerial Ace / Earthquake by the end.
-Roxanne: Ends her.
-Dewford to Brawly: Doesn't have any issues in the cave and even with Absorb it can defeat him pretty easily.
-Slateport to Wattson: Mixed here. The trainers have pokemon that Grovyle will muscle through, with the exception of Magnets. In Emerald, it is also more useful against Manectric than Combusken is, though obviously Marshtomp wins.
-Wattson to Flannery: Admittedly, it slows down here.
-Flannery to Norman: Grovyle solos the desert and is decent against Norman, whose pokemon all have low SpD. It can survive a hit from Slaking, which puts it into Overgrow range and helps out somewhat, though multiple hits are out of the question. In the end, though, Norman 2HKOs everything so that isn't unusual.
-Norman to Winona: Bug and Grass types galore, you won't be using it here. Nor will it be very useful in Winona's gym.
-Winona to T&L: It gets better here, IMO. It can take on the trainers on the land routes and really starts to shine in the ocean where everything is water-type. The Psychic-types don't have the bulk to take it on and it can wrap up the gym leaders pretty quickly due to them being part Rock.
-T&L to Water Gym: Again, more aquatic trainers = more wins for Sceptile. Leaf Blade covers what you need it to and Slam can honestly deal with everything else.
After this point, you face the E4, which is diverse enough to where I think the each starter shines equally well. Speaking of:
-Sydney: Sceptile kills his Water-types, isn't afraid of Mightyena, and also beats Cacturne/Shiftry with Aerial Ace.
-Phoebe: I think Swampert does best here, but Sceptile and Blaziken are equal.
-Glacia: Her Sealeo cannot take a Leaf Blade at all. Aurora Beam often fails to 2HKO and so Sceptile usually comes out on top, especially once Overgrow takes effect.
-Drake: Dragon Claw can sweep her team, though even Leaf Blade will do against his two Flygon.
-Champ: Sceptile owns Wallace, with the exception of maybe Gyarados. It is decidedly worse in RS, though it can still take on Aggron, Claydol, and Cradily.
I think Treecko is Top, but I could see the argument for High as well.
I'd also like to nominate Slakoth for Low. Truant sucks from the start, especially when you are weak to the first gym. You can do alright in the 2nd due to your high speed and power, but the 3rd gym resists you by way of Mags and Torkoal has high defense anyhow. Norman beats you, and then as a Slaking you are stuck with Truant again. It also needs the EQ and Shadow Ball TMs to be of use - it gets 1 hit every 2 turns, remember?
In-Game Name: Anthony
FC: 3309 2165 3231
I use legal hacks.