Dispersing Random Sampling in CSV through Python
There are many ways to implement this, but the abstract algorithm should be something like this.
First, to create a new CSV that meets your second critera about each state being drawn with equal probability, draw each row as follows. 
1) From the set of states, draw a state (each state is drawn with probability 1 / # of states). Let that state be s.
2) From the large CSV, draw a row from the set of rows where STATE = s. 
As you draw rows, keep a record of the number of rows drawn from a given state/city pair. You could do this with a dictionary. Then, each time you draw a successive row, if there are any state/city pairs equal to the cap set by the user, exclude those state/city pairs from your conditional draw in step 2 above. This will satisfy your first requirement. 
Does that make sense? If you get started with a bit of code that attempts to implement this, I'll happily tidy it up for you if it has any problems. 
If you wanted to do the "somewhat trickier" algorithm in which the probability of selecting a city decreases with each selection, you could do that without much trouble. Basically, condition on the cities within state s after you draw s, then weight according to the number of times each city in that state has been drawn (you have this information because you've been storing it to implement the first requirement). You'll have to come up with the form of the weighting function, as it isn't implied by your description. 
Again, if you try to code this up, I'm happy to take a look at any code you post and make suggestions.
I have a (large) directory CSV with columns [0:3] = Phone Number, Name, City, State.
I created a random sample of 20,000 entries, but it was, of course, weighted drastically to more populated states and cities.
How would I write a python code (using CSV or Pandas - I don't have linecache available) that would equally prioritize/weight each unique city and each state (individually, not as a pair), and also limit each unique city to 3 picks?

TRICKIER idea: How would I write a python code such that for each random line that gets picked, it checks whether that city has been picked before.  If that city has been picked before, it ignores it and picks a random line again, reducing the number of considered previous picks for that city by one.  So, say that it randomly picks San Antonio, which has been picked twice before.  The script ignores this pick, places it back into the list, reduces the number of currently considered previous San Antonio picks, then randomly chooses a line again.  IF it picks a line from San Antonio again, then it repeats the previous process, now reducing considered San Antonio picks to 0.  So it would have to pick San Antonio three times in a row to add another line from San Antonio.  For future picks, it would have to pick San Antonio four times in a row, plus one for each additional pick.
I don't know how well the second option would work to "scatter" my random picks - it's just an idea, and it looks like a fun way to learn more pythonese.  Any other ideas along the same line of thought would be greatly appreciated.  Insights into statistical sampling and sample scattering would also be welcome.