E lá vamos nós mais uma vez... :-)

Como eu já disse outras vezes, mais precisamente aqui e aqui: não existe uma definição única, canônica e universal sobre Orientação a Objetos (sugiro que leia esses links, e também os outros links que estão lá, em especial este e este). Mas só pra resumir:

Existem várias "escolas"/vertentes de orientação a objeto. Uma delas é essa que vc descreveu, que também se tornou a mais comum - e por isso muita gente acha que é a única, ou a "certa". Leia os links indicados acima para mais detalhes.

E mesmo dentro da vertente mais popular, ainda existem variações e controvérsias. Por exemplo, muitos autores consideram que existem apenas três pilares da orientação a objeto (encapsulamento, herança e polimorfismo). Alguns incluem a abstração como um quarto pilar, outros acham que é um conceito genérico demais e portanto aplicável a qualquer paradigma (e de fato, dá pra abstrair detalhes de implementação em qualquer linguagem ou paradigma, POO não é especial nesse sentido).

O próprio termo "objeto" é amplo e não se restringe a POO - como já citado aqui, cada linguagem define de um jeito. Em C, por exemplo, "objeto" é definido como uma "região de armazenamento de dados do ambiente de execução, cujo conteúdo pode representar valores". Ou seja, nada a ver com a definição "clássica" de POO.

Mesmo o uso de classes não é obrigatório, já que não é a única forma de se obter um código orientado a objeto (independente da vertente escolhida). JavaScript, por exemplo, usa protótipos (até existe a palavra-chave class, mas ela é apenas um syntatic sugar). Na verdade, até mesmo em C dá para fazer um código com polimorfismo, herança e tudo mais, só não é tão conveniente. As classes são apenas um mecanismo que facilita isso, mas não é o único (leitura adicional).

E ter atributos/estado também não é obrigatório, vide as classes utilitárias do Java e C# (como Math, que só têm métodos estáticos), por exemplo. Até mesmo ter atributos e métodos privados é discutível. Em Python, por exemplo, nada é realmente privado.

Sei que estou sendo pedante e que na prática, se o mercado "escolheu" uma das vertentes, então faz todo o sentido que os cursos se foquem em ensinar apenas esta. Mas se a ideia é, como vc mesmo disse, "compreender a base", acho importante pelo menos saber que na verdade o buraco é mais embaixo...