If a father's first wife dies (with or without children) and he remarries and had kids, is the first wife considered a (deceased) step-mother to the new wife's children, or simply "dad's 1st wife"?
No, the first wife would not be considered a stepmother to the second wife's children. The "step" relationship occurs where a person "steps into" the position of the holder of a normal natural relationship, taking over that role.
A second wife can "step into" the role of mother to a first wife's children, becoming a stepmother, but the first wife, being dead, cannot step into the role of mother to the second wife's children. The dead wife never had a relationship with the later children, and there is no common term for her indirect relationships with them.
If you accept the etymology that step-child in Old English was related to the word ástíeped meaning bereaved, then the children of the second wife have not lost a parent and so are not anyone's step-child.
Any attempt to create a family relationship between a dead person and ones not yet born who have no genetic (so-called "blood") connection seems to involve a serious problem in logic.