Yeah I get the random sampling idea. But imagine a limit case and that you were polling religion, and the country had 1000 different religions.

Even with the random sample of 1000, It’s almost guaranteed that some of the faiths won’t get reported and he won’t have data on them.

It would seem to me that something like this would require a larger sample size, not because of population size, but because of population complexity.

Obviously I’m a theorist and I don’t do the math

You're missing the point. It's not a representative sample, it's a random sample, meant to approximate a normal distribution in order to gauge a population mean re: some population characteristic. So if the question were, "Do you like apples or oranges?", a random sample of 1000 across a population should yield a reasonable estimate (within a margin of error) of how the population breaks on apples vs. oranges.

What you seem to be describing - necessarily getting a representative sampling of subgroups within a population - cannot be effectively done with random samples of 1000, especially given multiple subgroups. In that scenario (trying to get a representative sample of 1000 groups with one draw), of course a sample of 1000 is insufficient.

You're... ahem... comparing apples and oranges.