The full population size is generally irrelevant statistically (it applies to a "finite population correction"). Almost all the statistics you see presented publicly ignore FPCs by assuming the population is infinitely larger than the sample. Even when people take census reads of a full population they typically assume the population is a realized sample of a larger meta-population.
In general if you are seeing publicly presented poll data, sample size is not the thing that should be sending up red flags. Differential non-response and selection bias; sample frame matching or not matching the population; underlying noise in the conceptual measure; design effects caused by weighting; and many other components are all part of "TSE" (total survey error), which dwarfs the impact of sampling variation as a concern.
Now, mind you, subgroup analyses often do cut samples too finely... e.g., an N=500 sample subset to Men 65+ and people trying to make inferences but not properly reflecting either the sampling considerations or reduced subgroup sample size).
Let it also be noted from those classical calculations that larger samples are diminishing returns: N = 1000 -> 3.1% -> N = 5000 -> 1.4%. Five times the cost of surveying if not more, only a halving of the margin of error, and limited extra power to answer most real questions of interest.
> The bigger concern here is not sample size, it's whether the sampling was random
This confuses me a little. Aren't both of those things pretty important? To go back to your first sentence, a sample size of one could be perfectly random, but it will be pretty useless at telling us anything interesting about the population. Obviously that's a silly case, but what about 10 people? 100? I would venture to guess that a random sample of 100 out of 80,000 people would be unlikely to tell you anything useful about those 80,000 people, at least not without a margin of error much higher than the effect being measured. So that suggests to me that sample size is pretty important too.
> If we discovered that, say, every person above 40 hours a week wanted to be an employee and every person below wanted to be a contractor, it'd be an error to present a weighted average of the groups versus exploring policy solutions that reflect that heterogeneity.
That's a really good point. It's possible, and likely, that any single chosen classification is going to make a lot of people unhappy. Better might be to develop new rules and classes that fit the situation and different drivers' needs better.