if i was in your position and on a budget i would get the samsung galaxy s, the best current generation smart phone and pretty cheap.
i very nearly sold my iphone 3gs and got one recently, but i should wait for dual core, but dual core will be expensive.