Honestly, this is not a bad suggestion. It is a new idea that (as far as I know) hasn't really been discussed before by itself, so it is okay to have its own forum thread instead of necro-ing an old one. Personally, I do not believe that the King is OP, however, to those who hold that feeling, this would provide a stackable negative effect (which shields do not).
Question: would this be added on top of dropping shields or in replace of? If the King gets a penalty on top of shield drops then I think that might be a bit too much. For sake of example, I am assuming for the moment that it is in replace of.
With all that said, this penalty might be too extreme. Debatably, speed is one of the most important aspects to the game, and even just a small speed loss could be catastrophic. This is especially true once you start stacking kings, which is by far the favorite thing to do with kings (to the point where it is meme-able). And, as Janitorial Duties said, in long lasting games everyone hires at least one king, so it would just slow down the entire game with zero punishment to anyone since they are all the same speed.
In contrast though, it might not seem to be enough. Even with 4-5 Kings, a single-hire helmsman will not only counteract the speed boost but still be able to arrive faster than a normal sub. It might just be my opponents, but it seems that most of the people who hire kings also hire helmsman already, so it might not even affect them.
To summarize, I guess I don't quite know how I feel about this in the end. Depending on how it is played out, it could either be too extreme a punishment or one that is just as negligible as the shield drop (Maybe even worse if this allows the King to keep his shields now). In the end, I have to agree with Janitorial Duties and say that the penalty might just make the game less fun if kings slowed things down. Overall, it is a good thought and I overly enjoy thinking about stuff like this.

Zyxe? Now that is a name I haven't heard in a long time.