Back in the days of Duke Nukem, Quake and Unreal, we connected with no NAT using 1400 baud modems, if we were lucky ;-). Honestly though, I played direct (peer 2 peer) with Duke Nukem and conected over a centralized server for Unreal, but I hardly ever played Quake. I did this, with a 1400 baud modem and a phone-line that I paid for myself, with the earnings I made from a paper route job. It was the 90s and it was something special, for me at least.