between verizon or att? definitely verizon based on reliability.
cheapest plan? i pay about $40 for 100mms & 450atm. i'm grandfathered in for the unlimited data at $30. i hear they have a tiered plan now.
as far as phones go? the droid incredible is great if you don't want a physical keyboard. responsiveness seems greater than the droid2, droidx, others. the only issue i know about is that haptic feedback can quit working (intermittently) because of some defect during manufacturing. this is usually solved by them getting you a new phone. i have one myself and overall i'd say its at least 4.0/5.0.
if you don't want a tiered plan i think sprint is the only carrier that offers unlimited still to new customers. i dont know what they carry in android.