Crossing just doesn't seem to be a natural motion for beginners - whereas walking and pivotting, to a point, is.
OK, you could argue that this is exactly why beginners need to be taught it... but I prefer to get them walking as quick as possible. Crossing is clearly not an essential part of the dance, so I leave it until a bit later.
I agree with what you said about it being "unatural" and beginners resisting it, but I disagree that it needs to wait. It only takes about 2 minutes to show them the crossed position and say "The cross is a common element in tango, so if you feel that this position is where you are being led, don't resist it"
I also disagree that it is not an essential part of the dance. Can you dance without ever leading a cross? Absolutely. Are followers likely to experience that when they go to a practica or milonga? No. They are extremely likely to be expected to cross. Even when a leader fails to properly lead a cross, he might very likely say "You were supposed to cross" to the follower. (I've had this happen to me quite often)
I don't think you have to choose between walking and the cross. In fact, most beginners I've met get frustrated very quickly if you don't throw in something "tango'ish". After about 2 lessons on walking and technique, they're bored and ready to quit, wondering when they will get to learn TANGO!
And there is no shortage of instructors willing to show them not only the cross, but ganchos and boleos in the first few lessons, so you can't wait very long or the student just goes elsewhere. I'd much rather give the cross in lesson 1 or 2 than front ochos. I've no idea why some people think front ochos are good beginner moves. They are so hard to do without overuse of the arms, it seems like deliberately teaching bad habits to me! Its much easier to get people doing back ochos without the arms AND they at least won't violate LOD. But I've met several beginners who were taught front ochos in the first or second lesson.
Some of them come from other dances and are expecting to be shown "moves" so they certainly aren't stymied by the cross. Well, at least the followers aren't... the leaders take awhile to learn the proper lead. I can accept waiting to teach the leaders, but for reasons stated above, I think it leaves the followers at a disadvantage if you don't expose them to it quite early.
So the point where one might introduce it could vary quite a bit depending on whether one has (at one end of the spectrum) a large class of total beginners, both leaders and followers, OR (at the other end of the spectrum) a single follower taking private lessons.