Newton's 1st and 2nd laws weren't particularly revolutionary or surprising to anyone in the know back then. Hooke had already deduced inverse-square gravitation from Kepler's third law, so he understood the second law. He just could not prove that the bound motion in response to an inverse square attraction is an ellipse.
The source of Newton's second law was Galileo's experiments and thought experiments, especially the principle of Galilean relativity. If you believe that the world is invariant under uniform motion, as Galileo states clearly, then the velocity cannot be a physical response because it isn't invariant, only the acceleration is. Galileo established that gravity produces acceleration, and its no leap from that to the second law.
Newton's third law on the other hand was revolutionary, because it implied conservation of momentum and conservation of angular momentum, and these general principles allow Newton to solve problems. The real juicy parts of the Principia are the specific problems he solves, including the bulge of the Earth due to its rotation, which takes some thinking even now, three centuries later.
EDIT: Real History vs. Physicist's History
The real history of scientific developments is complex, with many people making different contributions of various magnitude. The tendency in pedagogy is to relentlessly simplify, and to credit the results to one or two people, who are sort of a handle on the era. For the early modern era, the go-to folks are Galileo and Newton. But Hooke, Kepler, Huygens, Leibniz and a host of lesser known others made crucial contributions along the way.
This is especially pernicious when you have a figure of such singular genius as Newton. Newton's actual discoveries and contributions are usually too advanced to present to beginning undergraduates, but his stature is immense, so that he is given credit for earlier more trivial results that were folklore at the time.
To repeat the answer here: Newton did not discover the second law of motion. It was well known at the time, it was used by all his contemporaries without comment and without question. The proper credit for the second law belongs almost certainly to the Italians, to Galileo and his contemporaries.
But Newton applied the second law with genius to solve the problem of inverse square motion, to find the tidal friction and precession of the equinoxes, to give the wobbly orbit of the moon (in an approximation), to find the oblateness of the Earth, and the altitude variation of the acceleration of gravity g, to give a nearly quantitative model of the propagation of sound waves, to find the isochronous property of the cycloid, and a host of other contributions which are so brilliant ad so complete in their scope, that he is justly credited as founding the modern science of physics.
But in physics classes, you aren't studying history, and the applications listed above are too advanced for a first course, and Newton did indeed state the second law, so why not just give him credit for inventing it?
Similarly, in mathematics, Newton and Leibniz are given credit for the fundamental theorem of calculus. The proper credit for the fundamental theorem of calculus is to Isaac Barrow, Newton's advisor. Leibniz does not deserve credit at all. The real meat of the calculus however is not the fundamental theorem, but the organizing principles of Taylor expansions and infinitesimal orders, with successive approximations, and differential identities applied in varied settings, like arclength problems. In this, Newton founded the field.
Leibniz gave a second set of organizing principles, based on the infinitesimal calculus of Cavalieri. Cavalieri was Galileo's contemporary in Itali, and he either revived or rediscovered the ideas originally due to Archimedes in "The Method of Mechanical Theorems" (although he might not have had access to this work, which was only definitively rediscovered in the early 20th century. One of the theorems in Archimedes reappear in Kepler's work, suggesting that perhaps the Method was available to these people in an obscure copy in some library, and only became lost at a later date. This is pure speculation on my part. Kepler might have formulated and solved the problem independently of Archimedes. It is hard to tell. The problem is the volume of a cylinder cut off by a prism, related to the problem of two cylinders intersecting at right angles). Cavalieri and Kepler hardly surpassed Archimedes, while Newton went far beyond. Leibniz gave the theory its modern form, and all the formalism of integrals, differentials, product rule, chain rule, and so on are all due to Leibniz and his infinitesimals. Leibniz was also one of the discoverers of the conservation of mechanical energy, although Huygens has his paws on it too, and I don't know the dates.
The mathematicians' early modern history is no better. Again, Newton and Leibniz are given credit for theorems they did not produce, and which were common knowledge.
This type of falsified history sometimes happens today, although the internet makes honest accounting easier. Generally, Witten gets credit for everything, whether he deserves it or not. The social phenomenon was codified by Mermin, who called it "The Matthew principle", from the biblical quote "To those that have, much will be given, and to those that have not, even the little they have will be taken away." The urge to simplify relentlessly reassigns credit to well known figures, taking credit away from lesser known figures.
The way to fight this is to simply cite correctly. This is important, because the mechanism of progress is not apparent from seeing the soup, you have to see how the soup was cooked. Future generations deserve to get the recipe, so that we won't be the only ones who can make soup.
The other parts, other than the inverse square, were clear already before Newton, or at least were easy to guess. That the force of gravity is proportionality to mass of a small object responding to the field of another comes from Galileo's observation of the universal acceleration of free fall. If the acceleration is constant, the force is proportional to the mass. By Newton's third law, the force is equal and opposite on the two objects, so you can conclude that it should be proportional to the second mass too.
The model which gives you this is if you assume that everything is made from some kind of universal atom, and this atom feels an inverse square attraction of some magnitude. If you sum over all the pairwise attractions in two bodies, you get an attraction which is proportional to the number of atoms in body one times the number of atoms in body two.
So the only part that was not determined by simple considerations like this was the falloff rate. I should point out that if you look at two sources of a scalar field, and look at the force, it is always proportional to $g_1$ times $g_2$, where $g_1$ and $g_2$ are the propensity of each source to make a field by itself. Further, if you put two noninteracting sources next to each other, this g is additive, if the field is noninteracting, essentially for the reasons described above--- the independent attractions are independent. So that the proportionality to an additive body constant you multiply over the two bodies is clear. That for gravity, the g is the mass, this was established by Galileo.
More mathemtically
Let's call the force law between the objects $F(m_1,m_2,r)$. We know that if we put the body m_1 in free fall, the acceleration doesn't depend on the mass, so
$$ F(m_1,m_2,r) = m_1 G(m_2,r) $$
So that the mass will cancel in Newton's law to give a universal acceleration. This gives you the relation
$$ F( a m_1 , m_2, r ) = a F(m_1,m_2,r) $$
We know that if we put body 2 in free fall, the same cancellation happens, but we also know Newton's third law: $F(m_1,m_2,r)= F(m_2,m_1,r)$ so that
$$ F( m_1, a m_2, r) = a F(m_1,m_2,r) $$
So you now write
$$ F( m_1 \times 1 , m_2 \times 1, r) = m_1 F( 1, m_2\times 1 , r) = m_1 m_2 F(1,1,r) $$
And this tells you that the force is proportional to the masses times a function of r. The form of the function is undetermined.
An independent argument for the scaling is that if you consider the object m_1 as composed of two nearby independent objects of mass $m_1/2$, then
$$ F(m_1/2 , m_2 , r) + F(m_1/2 , m_2 , r) = F(m_1,m_2,r)$$
Then the same conclusion follows.
These types of scaling arguments are second nature by now, and they are automatically done by matching units. So if you have a force per unit mass, the force between two massive particles must be per unit mass 1 and per unit mass 2.
This general argument fails for direct three-body forces, where the force between 3 bodies is not decomposable as a sum of forces between the pairs bodies individually. There are no macroscopic examples, since the pairwise additivity is true for linear fields, but the force between nucleons has a 3-body component.
Best Answer
Newton didn't say "change in momentum", he said "alteration in momentum", and whichever he said, this means clearly, and with no room for doubt, rate of change of momentum, the limit of small $\Delta t$ of $\Delta P \over \Delta t$. This was understood this way by everyone who read the book, there is no way to misinterpret if you follow the mathematical things.
The experiments of Galileo showed that bodies in gravity have the same acceleration. This means that the Earth is imparting changes in velocity to particles. The notion of "force" is already present to some extent in the theory of statics developed by Archimedes, and gravity produces a steady force in a static situtation, and this force is proportional to the mass. If you know force is proportional to the mass, and the acceleration is the same for all bodies, it is no leap to conclude that a force produces a steady acceleration inversely proportional to the mass.
The second law was not the major innovation in Newton, this was known to Hooke and Halley and Huygens for sure. Newton's innovation is the third law, and the system of the world, the special problems.