Modern out of order CPUs can do all sorts of things in parallel, having not only multiple functional units, but a lot of logic to check at runtime exactly which instructions really depend on others, so as to extract as much instruction level parallelism as possible.
The first microprocessors, of course, were strictly serial devices, which would finish one instruction before beginning the next. Even when pipelining was introduced, e.g. with early RISC CPUs like MIPS and ARM, each instruction would both start after, and end after, the previous one.
It seems to me that after pipelining, the next step in instruction level parallelism would be to try to do other things while waiting on a memory access. Once clock speeds get into double-digit megahertz, main memory is expected to be slow relative to the CPU (cache helps, but the hit rate is never 100%), and if you could start a load going, then do something else for a couple of cycles until it finishes, you could gain instruction level parallelism without needing multiple functional units.
What was the first microprocessor that could do ALU operations (independent of the value being loaded, e.g. in other registers) while a load from memory was in progress?