What's the best name for a non-mutating "add" method on an immutable collection?

Solution 1:

In situations like that, I usually go with Concat. That usually implies to me that a new object is being created.

var p = listA.Concat(listB);
var k = listA.Concat(item);

I'd go with Cons, for one simple reason: it means exactly what you want it to.

I'm a huge fan of saying exactly what I mean, especially in source code. A newbie will have to look up the definition of Cons only once, but then read and use that a thousand times. I find that, in the long term, it's nicer to work with systems that make the common case easier, even if the up-front cost is a little bit higher.
The fact that it would be "meaningless" to people with no FP experience is actually a big advantage. As you pointed out, all of the other words you found already have some meaning, and that meaning is either slightly different or ambiguous. A new concept should have a new word (or in this case, an old one). I'd rather somebody have to look up the definition of Cons, than to assume incorrectly he knows what Add does.
Other operations borrowed from functional languages often keep their original names, with no apparent catastrophes. I haven't seen any push to come up with synonyms for "map" and "reduce" that sound more familiar to non-FPers, nor do I see any benefit from doing so.

(Full disclosure: I'm a Lisp programmer, so I already know what Cons means.)