Generally a microcontroller has no MMU. A microprocessor may mean the same thing. The industry term for something with an MMU is an application processor (Cortex-A). There are other terms that can be used, but it will need to be specified.
There is some fuzzy area between MMU-less, small processors, and processors with no MMU but large enough to run Linux in a MMU-less way.
It's not very hard at all. The issue is exclusively licensing fees.
Cheapest depends. There are Allwinner parts that are $2? But with the move to RISC-V, we will see costs decrease further, probably so that a Linux-capable part is just as expensive or cheaper than an MCU.
Whenever possible I reach for a part that can run Linux, because most of any embedded task nowadays is connectivity. A lot of parts include a microcontroller on the same die for realtime tasks.
There is some fuzzy area between MMU-less, small processors, and processors with no MMU but large enough to run Linux in a MMU-less way.