Explicit balanced matrix
What you are looking for is a one-bit extractor for two independent sources: a function $E:[N]\times [N]\to \{0,1\}$, such that, provided X,Y are random variables with min-entropy 0.499*log(N), E(X,Y) is almost balanced. 

It's a notorious hard problem. For the parameters you want, I believe it was solved by Bourgain. See here:
http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf