That is why i like C. I can have my data structure and just add functions that can operate on those data structures outside of the data structure itself without worrying about coupling code to the data. Extra functions that can operate on the data may as well be inside a dynamically loaded plugin. Not feeling forced to put everything that can operate on a single instance of the data inside the same class. Not feeling forced to create a separate class to add methods that can operate on multiple instances of the data and hardcoding multicore support inside of it.
The new C++ (and Nim) have the notion of concepts which can mostly replace the many ways OOP was being abused. It is similar to type classes in Haskell. I advice you to read Alexander Stepanov's books.
You can have a data structure in a class, add certain concepts that the data structure supports and then create separate functions which can operate on these concepts outside of the class / object.
I agree with everything else you said, but the way I see it - when a paradigm cornerstone itself starts getting in the way of code organization, then that's a clear sign that paradigm itself is 'wrong', or more precisely, wrong when applied to this set of problems.
Oooooooh, look at that, I understand now what you meant :-D
Regarding your second paragraph - this is, looking from efficiency standpoint, the best approach. Additional gain is in access control: it becomes flat (ie. module-controlled), rather than having a class hierarchy in between, and then using messy constructs such as interfaces/mixins to achieve both code and type inheritance. Raise hands if you ever ended up in situation where you have to convert from one type to another, while the actual data they carry are precisely the same. Raise hands if you ever had to pollute an interface or a parent class with extra data, because a subclass somewhere contains exact data needed at the other part of the chain. This is friction - and it works against the developer/team. The larger the software, the worse it gets; it doesn't have to be that way.
Anyways, regarding last two points - yes, I'm very familiar with parametric polymorphism (it is a sole reason I use C++ for work, over C), and I have than half a decade of Haskell experience behind me. Trying to shift into Rust lately - its easier to find jobs.