AT&T
http://wireless.att.com is now letting you pre-order (choose your plan, text messaging, etc.) and pick your phone up in their store on 6/19 as early as 7 a.m. in some locations.
As per the $18 charge, it confirms that moving from a v1 to 3GS is only 1 $18 charge not two.
This is what I am going to do probably tonight or tomorrow. Will wake up early, get the phone, come home and load it, etc. and then go to work. Perfect scenario.