1) A genuine story or saint-making storytelling? Is it true that the dhamma is difficult to teach?
I'd assume the story is original to the time and that the Buddha had a hand in its creation. Did the events actually happen? No, but it's great representative storytelling. Does it make a valid point? Yes -- teaching the dhamma is a challenge.
2) How did the wide variety of people he was speaking to affect the form of his teaching?
As far as I can tell, he taught by trying to understand where people were in their lives and practices, and to speak to them in the paradigm they were familiar with, bending its terms to match his dhamma.
3) Why does he mention dependent arising? Is all the dhamma hard to see or just the bits he mentioned?
Now that's a tough question to answer, because the answer is complex.
As mentioned above, the things he specifically names are either directly dependent arising or liberation from it. The Buddha is naming the difficulties as seeing the process and how hard it is to imagine what it would be like to be free of it.
Is it actually hard to see? This might depend on one's background and life experience. To anyone who has never delved into any actual "science of the mind" the concept itself could be difficult. Even for those of us who started from science, a beginner's grasp of what's being said can result in an uncomfortable feeling in the gut (speaking from personal experience), and perhaps even a reluctance to grasp the full implications. And then once one has really understood it, seeing it in action -- finding ALL the ways it plays out in one's own life -- that's *really* challenging.
Is the rest of the teaching as hard to see? As mentioned by Ñāṇa, the rest of the teaching *is the same stuff* (it is all dependent arising and the escape from it) so in that sense, yes. But the rest of the teaching has more of an "entry level" access to it that provides a great "front door" for the teaching. It offers a place to start to see things in one's own life, and the skills to make that possible, so at that level it's not as difficult. But because all the apparently "entry level" teachings are actually trying to get us to see dependent arising and how to escape from it, it's really not as easy as it seems.