I think that one of your main problems may be that you're thinking of conversation as something it isn't. There is no procedure for success.

You can't create a procedure that maps out every branch in a conversation tree, no. But I think you are underestimating the ritualization and standardization of social activity. There really are patterns in how people do things. There are considerable norms, rules, and constraints. People who are intuitively social (whether they became that way earlier or later in life) may have trouble articulating these patterns.

Within these constraints, there are infinite ways to behave, and you can be as spontaneous as you want. Intuitively social people experience social interaction to be natural and spontaneous because their intuitions keep them within those constraints.

Conversation is "procedureless" in the same sense that musical improvisation is "procedureless." You can't map out the rules for improvisation in advance. But there are some chords that work well (or badly) after others that you can know in advance. You can know whether you are in a major or minor key, and if you have the concept of major/minor mode and key, then it will funnel your spontaneity in a direction that will create a harmonious result.

In contrast, a socially unskilled person is like someone improvising with concepts such as "mode" and "key." Their results are practically guaranteed to violate the constraints of what we consider to be good music. This of what happens when an untrained person plinks away at a piano.

While both conversation and musical improvisation are procedureless, there are procedures for learning those things. Musicians practice scales and etudes. Applying the same kind of process to learning social interaction is looked on as strange, because of the false expectation that people should be able to learn it naturally (even if the reason they haven't is because they were locked out of social interaction for years due to bullying and exclusion that was no fault of their own).

I don't think there is really such a thing as introverted and extroverted people at all. People are encouraged to think of these things as part of their "essential character" (TM) - or even their biology. And in some medical cases, this is obviously true (such as in autism).

Actually, introversation is a component of temperament that does seem to have a biological basis.

But for most people, it's not a lack of ability, it's a lack of will.

I agree that for most people with low social skills probably aren't biologically determined to be quite so bad at socializing. Even though people have different levels of potential due to biology, most people probably don't come anywhere near meeting their potential. But the problem isn't really their will; it's their social development and the associations that they have developed with social interaction.

Someone's present-day social skills are due to an interaction of biological and environmental factors. Temperament on its own generally doesn't determine social skills; instead, their temperament influences social experiences, which determine what level of social skills are learned. In the case of people with low social skills and different temperaments (e.g. introversion), these people generally got that way because their temperament made them "get off on the wrong foot" with their peers socially, often resulting in bullying, exclusion, or abuse. In another peer environment, even an introverted individual could develop social skills just fine.

The idea of an extroverted social animal who feels no fear is a false ideal, I think.

Actually, there are pretty large individual differences in susceptibility to anxiety. People with lower "anxiety threshold" (i.e. it takes less to make them anxious) really do have things harder. I managed to conquer anxiety at the level of social phobia, but to do I had to recognize certain challenges (and advantages) that my temperament gave me, and learned to cope with them.

To be pithy: "If at first you don't succeed, try and try again."

This works for some people once they have certain prerequisites for learning from their attempts at socializing. The trick is to get them to those prerequisites.