Mekkah, given that you rank Matthew as top tier in FE7, I'm surprised to see that you initially ranked Tentacool so low. In GSC, your only other alternative for Waterfall is Gyarados (unless you want to use Goldeen or something), and I doubt you want to waste a moveslot teaching it that. Also keep in mind that before you get Gyarados, you need a Surfer to get to Gyarados. I don't know what else you'd use for the task if you didn't start with Totodile, unless you picked up a Miltank or something. Tentacool is available as soon as you get an old rod (which is right after the first gym in GSC) and is covering four HMs (three of which are awful moves that you definitely don't want to have taking up a moveslot on one of your combat Pokemon). It's pretty much a staple and definitely top tier material.
I never really considered it like that because I do always put Waterfall on my Gyarados (I don't always incorporate him in my team, even though he's good). Or there's a random Dratini from Dragon's Den, or indeed a Goldeen from the Falls. G/S Tentacool isn't remotely close to FE7 Matthew. You need Waterfall like once, and when you do, there's plenty of options.
For Surf, there's Krabby encountered by Rock Smashing stuff as well as Tauros (mention the cow, mention the bull), and Krabby actually learns Cut and Whirlpool as well, so more points for him.
You seem to be under the impression that you are using one Pokemon for 99% of the game. This is not the case. You're using some kind of team that, while usually reasonably overleveled over most opponents, is not a L70 Pokemon by Elite Four that crushed everything in sight. Nidoking is still a monster in that design though.
I mean, by your logic, NidoranF deserves almost the same placement. Its stats are only slightly different, not enough to warrant being Bottom tier for sure. "NidoranM is simply superior" does not suffice.
For HM slaves being High tier simply for being so: no, I don't think so. They are usually not something unique, HMs are mostly there to give :some: kind of utility to crappy Pokemon. The utility of it is, in most cases, pretty much not possible to circumvent, and if it is it is very inconvenient, but all of them share it with a truckload of others. So like, the utility is 100% required, but there's 50 Pokemon available for doing the job, so it's more like 2% for each that can do it, assuming equal value for each.
There's problems with that approach, but in general I think it makes a fine demonstration of why HMs are there.
That said, even if your Yellow tier list held true, Pikachu isn't even required to train NidoranM. He can just run from every battle. Of course, without Pikachu you don't have a Pokemon, but that is kinda like "without Eliwood/Hector you would have Game Over".