I have nothing to add to the Ulam question, but I did want to give some speculations on early ideas.  The first is Emmy Noether and use of groups instead of Betti numbers and torsion numbers.  A group is, after all, a category and the use of groups is the sort of abstraction that categories are.  Although Vietoris was quoted as saying that of course they knew there were groups, but it wasn’t the style to say so.  But the homology groups of a space (as well as the homotopy groups) are certainly early examples of functors.  Although I am not sure when the homomorphism induced by a continuous map was known.

 

But the most interesting example is Garrett Birkhoff’s lattice theory.  First let me mention that in those early days of the XXth century, homomorphisms (between groups, rings,…) were always understood to be surjective.  It was only in the 50s that people started talking about homomorphisms into, which were explicitly allowed not to be onto.  This being the case, when Birkhoff looked at groups he saw the lattice of subgroups and the lattice of quotient groups (essentially the lattice of normal subgroups) and at rings, he saw the lattice of subrings and the lattice of ideals.  I have often wondered whether, had arbitrary homomorphisms been in common use, he would have discovered category theory rather than lattice theory.

 

Michael