I think you should've added a few of these to your post counterbond: lol
But part of the problem is that the US likes to be different. We still use the English system while the rest of the world including England has gone metric. When it comes to cell phone technology, GSM carriers are the standard in Europe and dominate the rest of the planet. Worldwide, there are far more GSM users than CDMA. So, who does Nokia and Sony make phones for, GSM only. Who gets all the cooler models because that's who cell phone manufacturers focus on? GSM
But here in the US, there are more CDMA users and more CDMA companies. Part of the advantage to CDMA is the carrier you're with, Alltel. Alltel provides a ton of rural coverage that nobody else bothers with. So we are in a bit of a quandry in the US, CDMA has far superior coverage and GSM has the cooler phones. Alltel also tends to focus on their systems where they have an 850 MHz cellular band license which provides a signal that gives better coverage than a PCS signal. With Alltel in your area, they would be very difficult to beat for coverage.
As for an unlocked phone, most CDMA carriers won't activate a phone branded by another carrier. Alltel doesn't lock any of their phones and it's fairly simple to get non-Alltel phones activated on Alltel, but then you will probably run into data problems and only voice and maybe texting will work. But be careful because some CDMA carriers such as Sprint do lock their phones.
The newest phones that Alltel has now are the Samsung U520 and the Motorola KRZR. The LG AX8600 is coming in March according to many others here on HoFo which has a very slick design.
If you're not satisfied with any of those, then I'm not sure what else could be done short of considering a coverage drop and moving over to GSM if they have a phone that suits your tastes better.