The Internet gateway selection problem is becoming very important as the number of Internet-connected devices increases and stresses the limited number of Internet gateway nodes. The gateway nodes often experience frequent performance fluctuations, and the best gateway selection candidate changes frequently with growing network dynamics. We propose GateSelect, a customized selection algorithm for each client node that not only provides the best-effort selection candidate but also ensures the global, balanced distribution of the gateway nodes. We utilize over the counter, lightweight calculations to optimize the client-side selection algorithm by combining classification, short term performance prediction, and randomized selection. We compare our algorithm with several baseline algorithms, and the experiment results show that our proposal provides better performance and balanced distribution of gateway nodes.