I think it also had to do with the fact that they're bottom feeders, as most fish spoil fairly quickly without proper care (though some are definitely worse than others - I think shark starts going bad literally as soon as the shark dies).

Like your second point, many bottom feeders are more likely to have parasites and, therefore, probably built up a reputation as being unfit for eating (though lobsters don't have any parasites that I'm aware of).