As of now, the iPhone (both versions IIRC) are incompatible with Verizon's network. More to the point, Verizon initially turned Apple down, opening the opportunity for AT&T to partner with Apple on the "super phone".
I don't know anything about 4G, but when it comes out between 2010 and 2012, the possibility exists that the cell phone providers here in the States could all use the same standard, thus making it possible for that version of the iPhone to be used on any network. Only time will tell on that one, however.
For now, the only two cell phone companies whose networks can support the iPhone are AT&T and T-Mobile. For the best possible experience with the iPhone, I would suggest you switch to AT&T. Yes, you can unlock the iPhone and use it on T-Mobile's network, but you won't have Visual Voicemail for one.
The new 3G iPhone, surprisingly, may actually be cheaper to purchase. The prices on eBay are a bit on the high side and even with the ETF from Verizon (assuming you're on Verizon now), you may actually save a bit of money over the pruchase price and shipping costs of purchasing a 1st gen iPhone off eBay.