We have pretty good records of letters from Paul from the second half of the first century (as well as a bunch of frauds, but AFAIK there are several that stand up under analysis as being written by the same person at a very early date), who (in several of those letters) was adamant that his sect believed in an individual Christ in the flesh. So if the legend of the historical Jesus sprang from whole cloth, it did so pretty quickly- not to mention the synoptic gospels, which the most skeptical of scholars still date to around 100 AD.
More generally, I'd caution fellow atheists against getting drawn into the existence-of-Jesus debate in meatspace: unless you've done a lot of relevant study (and why on earth would you?) you won't be able to point to basic evidence that your interlocutor has heard of, only to the statements of experts that they won't trust. Better to say "Well, I'm not sure there's enough evidence even to conclude that there was a historical Jesus- but even granting that there was, and that there came to be a group of followers convinced of his divinity, that's still nowhere near the kind of evidence to make Christianity a viable hypothesis, compared to the hypothesis that it was just a rabidly successful example of what happens within cults." That's a much better place to draw up battle lines, IMO.
The overarching problem you outline in your second paragraph - the more general problem, faced in many fields, of having to compress a degree into a few sentences to properly answer an objection - is sadly well known. This is why the RationalWiki article (which is still patchy as heck) is a sea of nuance and caveats - it attempts to get it right in less than a book for an audience who are frequently just realising that there's actually historical thought on this matter (and look how that line of inquiry worked out for Lukeprog!). I'm very much looking forw...
To break up the awkward silence at the start of a recent Overcoming Bias meetup, I asked everyone present to tell their rationalist origin story - a key event or fact that played a role in their first beginning to aspire to rationality. This worked surprisingly well (and I would recommend it for future meetups).
I think I've already told enough of my own origin story on Overcoming Bias: how I was digging in my parents' yard as a kid and found a tarnished silver amulet inscribed with Bayes's Theorem, and how I wore it to bed that night and dreamed of a woman in white, holding an ancient leather-bound book called Judgment Under Uncertainty: Heuristics and Biases (eds. D. Kahneman, P. Slovic, and A. Tversky, 1982)... but there's no need to go into that again.
So, seriously... how did you originally go down that road?
Added: For some odd reason, many of the commenters here seem to have had a single experience in common - namely, at some point, encountering Overcoming Bias... But I'm especially interested in what it takes to get the transition started - crossing the first divide. This would be very valuable knowledge if it can be generalized. If that did happen at OB, please try to specify what was the crucial "Aha!" insight (down to the specific post if possible).