Blackberry Storm (if unlocked, can be used with any network because it’s both CDMA and GSMtakes Sim)
iPhone 3G
HTC HD2
Are they good? Yes. But, they require extreme care if you’re as conscious about its appearance as some of us. Not to mention they’re more fragile than your old cell phones, so dropping one would probably end in immediate death. (Invest in an extended warranty.)
Nokia 5530 is probably the best in that range, unless you want 3G, for which you should get 5800. Star is ok, but it has a proprietary OS which I really hate. LG Cookie is cheap too but that too has a proprietary OS.