Does that means that HALF of the ~296 private keys is in first 2159 and other HALF is in 2160 - 2256 space?
I don't think so. An address is a very big number, and there are plenty of programs and algorithms to "pick a number".
I don't know if all of them ensure an uniform spread (especially when human-generated seed is used).
Also, let's say that theory tells that if you have the same chance to roll any number of a dice. If you'll get a dice and roll 12 times, most probably you will not get each number twice. You'll tell that you need to roll 6000 times to get close results and that's right. Although I don't agree with the term "randomly" used by @Dabs, I agree with him: we have so few addresses compared to the possible address space we cannot talk yet about getting even close to an even distribution.