Well, what I had in mind is the thought that most forms of fish would still be fish. The idea of most creatures in Fallout is to take an existing creature and dress them up.
Mirelurks, for instance, are mutated horseshoe crabs - a species that's extremely old and persistent enough to survive a nuclear holocause, and then mutate into a bipedal, landwalking species.
Any species that would survive and mutate in the ocean would also have to be just as hardy and dangerous. Most fish species would die out, as much of their primary food supply either stops growing or becomes contaminated, if they don't die out themselves, and that would include many species of sharks and whales.
Many of the starfish's predators might die out from the nuclear fallout early on, so it might have some luck in terms of having a shot, though again, a type of giant mutant starfish would still qualify as a tentacle monster in my book.
In the same vein, I'd imagine many deep sea creatures would have a chance, before nuclear material finally filters down into the murky deep. And seriously, a lot of those deep sea creatures are terrifying to begin with.
OF course, this doesn't preclude the idea of genetically modified creatures escaping their pens (a la Deep Blue Sea). Mutant sharks, or, perhaps even more darkly, mutant dolphins, plying the waters. Dolphins, specifically because of the history the US Navy had in using them for experimentation.
And we don't need mini nukes to blow stuff up 