500 voters?! There are 700,000 people in that district. Better call more to get a more accurate picture.
SURVEYUSA was the 2nd most reliable pollster in 2002.
You have made a very common mathematical mistake. If your sample of 500 is truly RANDOM, it gets just as good a picture of a 700,000-person Congressional district as of a 70,000-person city or a 7,000,000-person state.
It is true that you sometimes have to do more work to ensure randomness if you are polling a larger area, but you don't need a larger sample.