Microservice usually means distributed system. A distributed system is more complex than a non-distributed system since it has to do everything the non-distributed system has to do and, additionally, handle all the distributed problems. Microservices just hide the complexity in places where people don't see them if they take a cursory look over the code, e.g. what is a function call in a monolith can be a call to a completely different machine in a microservice architecture. Often they look the same on the outside, but behave very differently.
The hierarchy of simplicity is: Monolith > multithreaded[1] monolith > distributed system. If you can get away with a simpler one it will save you from many headaches.
> I've worked at companies that have monoliths that are 50x more difficult to work on because of the size. Some of them millions of lines of code. Nobody really knows how they work anymore.
That is a bad architecture, not something inherent to a "monolith". There's probably also a wording problem here. A monolith can be build out of many components. Libraries were a thing long before microservices reared their ugly heads. What you describe sounds more like a spaghetti architecture where all millions of lines are in one big repository and every part can call every other part. Unfortunately, microservices are not immune from this problem.
[1] or whatever you want to call "uses more than one core/cpu"
This is a false assumption. Some problems are distributed. Sometimes you'll have an external data store or you'll need to deal with distribution across instances of the monolith. You really run into pain when you build a distributed system in your single monolithic code base and your monolithic abstractions start falling apart.
In my experience you end up solving these problems eventually, monolith or not. You might as well embrace the idea that you're deploying multiple services and some form of cross service communication. You don't need to go crazy with it though.
Anyway, if your problem requires a distributed system, congratulations, you'll have to go to the top of that complexity hierarchy, and will have to solve all the problems that come with it.
That doesn't change anything about there being more problems. You just don't have any other option.
A core skill problems on a team that would prevent building a maintainable monolith do not go away because you've added more things for them to manage.
However, if the organization is not capable of structuring the monolith, why should it be successful with microservices?
Such organization may lead to sharing data stores and custom libraries between microservices and that's when the real fun begins. Maybe even trying to deploy all of the services atomically to not worry about API compatibility.
But 1 semi-complex system > 10 simple systems. Especially when you consider the points of integration between those systems increases geometrically with the number of systems.
I've worked at companies that have monoliths that are 50x more difficult to work on because of the size. Some of them millions of lines of code. Nobody really knows how they work anymore.