The combination of a really nice multimedia phone for cheap (or free) coupled with a cheap monthly plan is pretty difficult. You can get nice phones cheap but they'll get you on the monthly fees, or you can spend a bunch on a nice phone and then figure out ways to get the cheapest plan for them. You don't mention where you will be or how many minutes you use in a month, but that's ok because, once the US moved to 4 dominant carriers, all the deals (except for Sprint's SERO - and that's gone now too) all evaporated. Ah, the joys of consolidation.
If you want an iPhone, about the best deal you can get on an iPhone is to get a used 4GB model on Ebay - either unlock yourself (which is easy nowadays) or buy it unlocked. Then get a pre-paid phone card with data for a GSM phone using either T-Mobile or AT&T or a local GSM equivalent (some of the smaller carriers are GSM too). You'll probably want data so then include the AT&T $20/month pre-paid data plan - and then use IM instead of SMS/texting. You can get this as cheap as $25/month with no included minutes.
Or just get the abovementioned 4GB unlocked 1st gen iPhone with a plain T-Mobile voice plan($30), add in the T-Zones unlimited data hack for $5/month, add in the 200 SMS's for $5 and you can get 300 minutes per day, unlimited night and weekend, unlimited data and 200 texts for $40/month.
Beyond that, the Blackberry Curve is very nice, with a bright screen and a keyboard. You can it for free from places like Amazon if you sign up for a new plan. But if you get a blackberry, they will want to tie it to a "Blackberry plan" - which runs $15/month to $30/month on top of the voice plan, although you get unlimited email and data, but no SMS texts. So, this will run you $40(voice) + $20(BB data) + $5(texts) => $65 per month.
AT&T is usually more expensive than T-Mobile, but has a 3G network and (normally) better coverage. But if we want cheap... then it's best to avoid AT&T aside from the pre-paid GoPhone plans. T-Mobile offers the Wing and the Sidekick phones both of which are reasonably neat phones with big screens and keyboards. AT&T has the LG Shine, and the Samsung Glyde. Verizon has the Moto Q and the forthcoming Blackberry Storm touchscreen. Sprint has the Mogul PPC-6800 which is pretty cool. T-Mobile is usually cheaper than AT&T, Sprint is usually cheaper than Verizon. Cricket - if they are where you will be - offers inexpensive data plans and good calling plans - but they are CDMA so no iPhones. In fact the Cricket phone selection is pretty bland in my opinionated opinion. Alltel is usually pretty cheap and the have the Moto Q9c for free and the LG Glimmer (haptic touchscreen) for $50. The Blackberry Pearl is an underrated very nice phone... but they'll want to tie you to the expensive blackberry plan... although if you buy one unlocked on Ebay you can get whatever plan you want...
Lots of options... probably too many.
Facebook
Twitter