This depends on your definition for "the norm amongst all humans".
If you want absolutely 100%, every-single-human-of-billions, you can't reasonably achieve that on a global scale. There will always be outliers, isolated populations, purists, etc., that will spoil the idea of perfect coverage for basically any trait less critical than things like "born with a nose". Will migration over time from a single starting populace realistically reach and interbreed with every tiny community in the Amazon rainforest, on the Pacific islands a thousand miles from anywhere, and other such remote places?
However, if you're simply looking for "considered normal/ordinary" or perhaps "single most common trait of the options available", you've got a much more practical target, to the point where a starting population of a thousand hybrids would likely be severe overkill. Note that I'd recommend a minimum starting populace of hybrids of at least a few dozen for realism no matter what figure any mathematics give you, simply because you want to avoid the damage that a random accident in the first or second generation could do to the spreading efforts; any single individual can get an infected injury, suffer a bad fall down the stairs, be born infertile, get killed in a fight, and so on and so forth, and losing even one individual from a breeding population of four would be catastrophic.
For the former, the definition will be a little subjective, as there's no hard line on what overall percentage it takes for something to be considered "normal". Brown, black, and blonde hair are all considered "normal" in most regions (red hair being consistently a minority), and between them those represent the lion's share of humanity. Given that you're talking about upwards of a dozen possible animal traits that might manifest across however many different hybrid types you start out with (your question implies multiple species had human hybrids created), only one of which needs to show for any given individual to meet your goal, adequate coverage becomes easy.
For the latter scenario, of being the most common option, this generally depends on how many different categories are possible (like colours of hair, for instance). In your case, you're looking for a simple "has one or more animal traits" versus "has no animal traits", in which case your target for coverage is 50%. Given the example of Charlemagne provided by ETam in their answer (adequate coverage of Europe within about 1300 years or less), your timeframe of 2000 to 3000 years is eminently plausible with an initial populace of even a handful, and might be so even if you picked out a single specific trait, provided these hybrids did any serious migration.
Math time: You've specified these are all dominant traits, so not only will any child of a hybrid qualify, so will nearly all their future descendants for multiple generations even if no other hybrids enter the picture. This makes for exponential spreading power.
Let's say there are four possible traits of a given hybrid, and you've stated that your goal is met if even one of them shows in a person. I'm assuming a single gene for each trait to keep this simple (and ignoring edge cases like random mutation), although in practice genetic inheritance for a specific trait is often more complex. Every child will have one copy of all four relevant genes. Each grandchild has a 50% chance for any one of these genes. The odds of not having any of them are (1/2)^4 = 1/16, so only one in sixteen grandchildren will have zero (or all four): the average case is two traits, and there will be four with three traits and four with just one.
For the next generation, given the average case of two traits, the odds of inheriting none (or all) become (1/2)^2 = 1/4, so on average three-quarters of the great-grandchildren will have at least one trait even if everybody was marrying pure humans, and the chance of having one animal trait for a given great-great-grandchild still averages out to 50%. Realistically, some of those children will be marrying other hybrids or descendants of such (or even each other: marriages between first cousins or second cousins were historically fairly common, and are still practiced in a number of countries), so your set of animal traits will reinforce and proliferate themselves with impressive speed even if you only started with two or three hybrids in a given region.
Conclusion: If your target is "absolutely 100%", your goal is implausible unless you go back to near the start of homo sapiens. If your target is merely "widespread to the point of being unremarkable", your goal is almost trivial with your given conditions.
Note: I'm assuming that in your world, sufficient people were attracted to your hybrids to breed with them throughout the generations, that they weren't shunned as mates for being considered unappealing/unattractive, that they didn't get exterminated out of fear or racism, that their descendants didn't face serious purge efforts or witch hunts, etc.; in short, that social and cultural factors didn't mess with their chances to have children. Whether or not that would actually hold true is a topic for another question entirely: I'll merely point out that history shows a great many examples of persecution of groups for various differences of opinion or appearance, and your hybrids would certainly be a visible target for such efforts, so you should consider how that problem is addressed in your world.