Yes. For example the Arduino 328P ("Uno" boards) has 31.5k of program flash available to you, while the ATMega 2560 has 256k (minus again 0.5k for the bootloader). The STM32F411RE, a Cortex-M4, has 512k.
In embedded development you can forget the overhead due to binary formats such as ELF (while the toolchain might output these as an intermediate, what is flashed is just the relevant sections), but if you are doing things like loop unrolling all over the place, you're going to get less functionality for static program space.
This is why ARM and PowerPC have "embedded" variants of their ISAs. What this means in practice is a compressed form of their instruction representation. Why? If you have compressed instructions, you can fit more of them in program flash. So both Thumb and VLE are variable length encodings. Thumb, for example, can use 16 bits for many instructions, i.e. two bytes, whereas ARM by default would simply take four bytes for all instructions. (For the avoidance of confusion, they still "address" 32-bits of memory and are thus still 32-bit microcontrollers). PowerPC's VLE is similar.
The driver here is cost. You could put in more program memory (the address space has plenty of room) but that costs more money, and when you don't need it, why do it?