A pull up/down resistor (or an on-chip current source) is used to give a certain "default" value to a node which would otherwise not have a default value but does need it.
Such a value is needed when the node feeds into a CMOS logic input because then undefined erratic behavior can occur as such a CMOS input has an extremely high input impedance so the voltage on the node can be easily disturbed making the gate "flip" randomly. In this case a pull up/down sets a default value and prevents random "flipping".
Is it needed everywhere ?
No because many nodes will be connected to some output which will provide a default value. Only nodes which could be high ohmic at some point and connect to a CMOS input need a pull up/down.
You mention that a microcontroller's output level is unknown at startup. That can be true if the uC starts with the outputs in HighZ (high impedance, Tri-state) mode. Most uCs do this. After initialization the uC should define the output state properly. If the circuit connected to the uC's output cannot handle the HighZ mode properly (even for a short time) then a pull/up down is indeed needed.
A different use for pull up/down resistors is with open collector or open drain outputs. These outputs can only pull the voltage up or down. For example an open collector NPN can only pull the output down.
To be able to make a "high" signal a pull up resistor is needed.