0

Try this, we're using it on a daily basis
Nest[Merge,f,n]
To your starting data, slightly modified (strings vs symbols):
peopleFacts = <|"alice" -> <|"age" -> 29, "shoeSize" -> 7|>,
"bob" -> <|"age" -> 27, "sex" -> "male"|>|>;
And new facts:
newFacts = <|
"steve" -> <|"hairColor" -> ...