I'm not sure if your main interest lies on the question on the title of this thread or in the question you pose near the end of your text. I'll try to answer both, in spite of not being an expert neither on GR nor on the education on physics.
Why is it, if it is true, that GR would have taken many more years to discover, had Einstein not discovered it?
I agree with you and the comments to your question in saying that GR would most likely have emerged, in the following years (though "how many years?" is a question which I don't think anybody can answer) as a consequence of the equations given by Hilbert in the paper he published at almost the same time. A detailed account on this subject can be found on the following Physics SE question: Did Hilbert publish GR before Einstein?, and I can quote Pais' biography of Einstein on this subject (for a beautiful account of this particular episode of the development of GR, check chapters 11-14 of "Subtle is the Lord":
Let us come back to Einstein's paper of November 18. It was written at a time in which (by his own admission) he was beside himself about his perihelion discovery (formally announced that same day), very tired, unwell, and still at work on the November 25 paper [the paper called "The Field Equations of Gravitation"]. It seems most implausible to me that he would have been in a frame of mind to absorb the content of the technically difficult paper Hilbert had sent him on November 18. More than a year later, Felix Klein wrote that he found the equations in that paper so complicated that he had not checked them. [...]
I rather subscribe to Klein's opinion that the two men 'talked past
each other, which is not rare among simultaneously productive
mathematicians'[...] I again agree with Klein 'that there can be no
question of priority, since both authors pursued entirely different
trains of thought to such an extent that the compatibility of the
results did not at once seem assured'. I do believe that Einstein was
the sole creator of the physical theory of general relativity and that
both he and Hilbert should be credited for the discovery of the
I am not sure that the two protagonists would have agreed [included as
a funny note].
Subtle is the Lord, Chapter 14, page 260. I think this supports my previous statement quite well.
Why isn't general relativity the obvious thing to try after special relativity?
I think this question can only be answered if we are talking about the teaching of the subject to undergrads in college. If we were talking about one teaching him-/herself GR after learning SR, I believe that the answer would be "well, mostly because one doesn't want to/couldn't do it; in fact, one could have done it before", or something along those lines, which doesn't quite help.
When talking about teaching SR to undergrads, you've got to understand this: there isn't a standard for teaching the theories of Relativity to undergrads (written as an as-of-yet undergrad). We mostly get taught versions of the theory with not so much emphasis on the mathematical structures lying below the subject, and get mostly taught to do calculations and think of the dynamics. So we, in these cases, don't always get to know the concepts of metric, of flat spacetime (which we actually use, but almost never think about it for the course), of curved spacetime, among others.
Add to that the fact that, in many universities (such as mine and the one's of many of my acquaintances), we don't get to learn much math (besides Calculus, some Linear Algebra and Complex Variables) before plunging into the vast world of physics subjects, so we are not in a position to say "oh, of course, this concept that I saw when learning SR can be, by analogy with these things which I haven't learned, extended to a more general (and complicated) one, which would link to some variational principle in order to get some new and complicated tensor equations, which we can't solve".
So well, if you see it from a mathematician's point of view (yours), the next step from SR is quite obvious because of the mathematics you know, but if you are a physics undergrad, who has (most likely) not had an intense training in mathematics, you are certainly not going to be able to take that step. Though I may be generalizing horribly, but all that I've said is true, in my experience.