The magnitude of Cain's crime was immense.
According to the record in Genesis, the first children of Adam and Eve that we know of are Cain, Abel, and Seth. At the time that Cain killed Abel, then, it is plausible to conclude that Cain just killed half of the rest of the human race. It's bad enough to kill someone else, worse to kill them over the quality of sacrifices and God's acceptance of them, worse still to kill your own brother, and then you add in the fact that Cain killed one of only four humans alive at the time. Cain has committed one of the greatest crimes imaginable. He is very much deserving of death, and he has good reason to be fearful of others that might want to take vengeance.
The identity of the others.
Who are these others, you might ask? Well...
3 When Adam had lived 130 years, he had a son in his own likeness, in his own image; and he named him Seth. 4 After Seth was born, Adam lived 800 years and had other sons and daughters.
6 When Seth had lived 105 years, he became the father of Enosh. 7 After he became the father of Enosh, Seth lived 807 years and had other sons and daughters.
~ Genesis 5
I would conjecture that Cain lived about as long as Seth, give or take a couple hundred years.1 Supposing somewhat arbitrarily that Cain lived 800 years, in that time the family tree would be at least six levels deep just from Seth's branch. The following people would have been born in Cain's lifespan: Seth, Enosh, Kenan, Mahalalel, Jared, Enoch, and Methusaleh. This is not counting the other sons and daughters each of them had. Including Adam, incidentally. To get a rough, lower-bound estimate for the number of descendants of Seth alive in Cain's time, I'm going to assume that each son had five children, three of whom are sons.2 This leads to at least 1215 people alive in Cain's lifetime who would have had reason to find him and kill him.
That's a lower bound. Adam and Eve also had "other sons and daughters" (which would bump up the population to at least 4000), and Cain himself had progeny. We're talking at least 5000 people living before Cain died, a significant portion of which might want to kill him. It is also quite possible that Adam and Eve already had other children by the time they had Cain, and in either case, Cain was probably smart enough to realize that there would be other people that would want to kill him, even if they hadn't been born yet. Hence, his fear is justified.
1 Now that's a phrase you won't hear often regarding human lifespans.
2 Given the lack of a prohibition against incest, which didn't appear until Moses' time3, I'm going to assume that the daughters very well might have married brothers/cousins. It's easiest to leave them out of the calculation (and I'm calculating a lower bound anyway).
3 Leviticus 18:8-18 and Leviticus 20:11-21