I went to AT&T and saw that they had set up a little area with a bunch of cases and stuff (for the new iPhone), but they looked pretty crappy and it was maybe like 1/10 of the selection of an Apple store.
Simple solution to this. Buy a 3G iPhone at an AT&T store then head over to the nearest Apple store. Waltz in past the people STILL waiting in the line for a 3G iPhone. If your feeling like a bastard, whip yours out and tease those who have been waiting in line for hours. Pick a case from the vast selection and walk out.