Your question is about sample size for a finite population. But the first thing you need is the sample size required in an infinite population, which can then be used to calculate the sample size for a finite population.
In a survey of an infinite population, the formula is: $n=(z^2pq)/d^2$
$n$, sample size
$z^2$, confidence level, usually 1.96
$p$, proportion of the population with a characteristic, if unknown use 0.5
$q=1-p$, proportion of the population without a characteristic
$d^2$, error level (aka margin of error), usually 3%, but 1% or 5% can be used.
Error level becomes the most important factor because the lower the level of error, the bigger the sample size required and visa versa. Therefore, the sample size for an infinite population with 3% error is: $(1.96 \times 0.5 \times 0.5)/0.03^2=1,068$. Further, the error level means that results have an error of +/-3%, in this case. This means that if 48% of people in the survey were male, then the range possible is 48% +/- 3%, or 45% to 51%.
The next step is the formula for sample size for a finite population: $m=n / (1+((n-1)/N))$
$m$, sample size for finite population
$n$, sample size for infinite population (1,068 from above)
$N$, finite population size
Using the example of $N=1,000$, the sample size required with 3% error would be $1068 / (1+((1068-1)/1000))=517$, or 51.7% of the population.
If you used 25% of the population, the error level comes out as 5.4%. This error level may be fine based on previous surveys. With surveys there is always a trade off between the level of error you are willing to accept and the costs of doing the survey.
None of this factors in the response rate (if using a simple random sample). To find out how many people need to be contacted, you divide the sample size by the expected response rate. For example, if the previous response rate was 65%, the you would need to send the survey instrument to $517/0.65=796$ people.
Things get more complex if you want to divide up the population by department (known as stratification). Basically, you need to treat each department as a separate finite population if you want the data to be accurate to each department, which may not be practical. But you could do a stratified random sample instead of a simple random sample, where 50% of the sample is randomly selected from the department with 50% of the population, and suitable percentages are randomly sampled from other departments. It will mean that your sample size will increase slightly because you need to round all decimal places up (you can't survey 0.1 of a person). However, the results should be examined at the population (company) level and not at the department level because there will not be enough responses from each department to be accurate.