Since I review quite a few phones, my answer changes every week . Right now I'm using a nifty Nokia S60 smartphone that just came out-- the 6120 Classic. It's quite cheap from importers, unlike most Nokia S60 phones (around $320), has a 2MP camera and is really small. We'll have a review of that up next week.
If you're going to set up an AT&T account (or 2 lines, one for the Advantage and one for a cell phone) then you'd probably want to get their subsidized phones. Do you want a smartphone, or a regular feature phone? The BlackJack is pretty cool and fairly cheap with a new contract and the Cingular 3125 or Nokia N75 are both smartphones with a flip design.
Editor in Chief, MobileTechReview