I'm just tickled by this, as one sometimes is by the errata found within the rulebooks ...
Giant Sturgeon have more hit dice than Black Puddings (barely). At HD 10+2, a giant sturgeon has slightly more hp on average than a black pudding (HD 10), the same "to hit" chance, and does a respectable 2-20 damage with its bite compared to a black pudding's 3-24. The sturgeon also swallows a character whole on a "to hit" roll of 18+, which does an automatic 2-12 damage/round and forces a save against death ray, or the character is paralyzed (if not paralyzed, they can cut their way out ... DM's discretion how, though, beyond a -4 "to hit" against AC 7, as there's no damage threshold). Sure, giant sturgeon can be hit by non-magical attacks and don't split into smaller versions of themselves, but they're still terrifying monsters.
Of course, all the giant fish in D&D are terrifying. A Giant Catfish has more hit dice/hit points than a Hill Giant, a better "to hit" chance, and 5 attacks, one of which does as much damage as the hill giant's. And Giant Rockfish have HD 5+5 and 4 spine attacks, each with deadly poison, which makes them just that more terrifying than real stonefish (which are also deadly poisonous, but at least are normal fish-sized).
Outside of B/X, in the AD&D Monstrous Manual (2e)--I use all my sourcebooks when keying dungeons for variety's sake--the Giant Crayfish not only has HD 4+4 against the Ogre's HD 4+1, but the crayfish has two attacks, each doing more damage than the ogre's one attack (2-12/2-12 against 1-10 OR weapon +6). On top of which, the crayfish surprises with a -2 penalty for the players! And Giant Carp have from 8-12 hit dice ... those poor dwarves in Dwarf Fortress ...
One other thing that tickled me was that sharks in the blue Expert book are listed as having 18" speed, rather than the typical breakdown into B/X, i.e. "swim 180' (60')" for 18". That's the only speed in inches I've yet come across in B/X.
I don't think that I would really use these creatures as "typical" wilderness encounters on the water, on any kind of river or lake that sees civilized traffic. Their hugeness, represented in terms of hit dice, seems to represent something ancient and awful (e.g. a centuries-old sturgeon lurking at the bottom of a high mountain lake, unplumbed by man), or to mechanically iterate the horror one feels looking down into the blackness of unknown depths (say, a silent black lake in a vast and gloomy cavern, far below the surface of the world) and to fear what might lurk beneath.
The only place I can see such monstrosities existing near communities of men is as "gods" or spirits, venerated by the local tribe, offered sacrifices--perhaps manacled prisoners dropped over the gunwales of canoes from the middle of an alpine lake, or hacked into pieces and scattered like chum across the bloodstained waters. And naturally, such "gods" would also have treasures devoted to them, gold, gems, and even "lake swords" cast into the deeps to buy the god's benevolence--or tolerance--for the local fishermen; treasures ready to be seized by any adventurers foolhardy enough to face 10+ hit dice fishes and ridiculous enough to have waterbreathing as their only 4th level spell!