The thing is though, once Seedot evolves, which is pretty likely before/after Roxanne, it performs fine as a Nuzleaf. Gym matchups be damned, but Nuzleaf is able to hold its own against the common route mons, especially with Fake-Out softening (a bit better than Lobre can). Overall, I think Lombre and Nuzleaf belong in the same tier in the end, whether it is E or D. Neither one has positive matchups over the other and Nuzleaf even has the advantage of evolving early and possessing the Dark type, which the few number of threatening fighters/bugs proves useful. Ludicolo eventually gets Surf and Ice Beam, but Shiftry can take on almost Phoebe's entire team. This puts them on about equal footing in my eyes. Ludicolo gets the bulk and advantageous typing, but Shiftry gets the better offenses plus the role as a psychic killer.Seedot could maybe move up, but I think the sheer amount of exp you need to baby into it so that it’s actually able to contribute when given the Leaf Stone means it fits in better with E rank.
EDIT: Your description of early Seedot seems overly exasperated, as switch training it before it gets Bullet Seed is really no big deal. After it gets that, there is not much difficulty in using it as a regular mon, plus Nature Power and evolution is on the horizon. I fought the three trainers I could on Route 116 (before Rusturf Tunnel) before facing Roxanne's gym, and it fared fine enough. I don't think that is totally unreasonable considering its short proximity to Rustboro. Again, it's not the most efficient Pokemon you could use, but that's why I'm arguing only for D-tier. It obviously has its drawbacks but Nuzleaf is an okay Pokemon to use. What E-tier says to me is that it is something that never pays off in the end, but Shiftry pays out in the lategame. I don't think it's less compelling than any of the other currently D-ranked Pokemon, and I don't think it's as bad as the similarly available Poochyena.
PS What do you think of Ninetales dropping?