I am currently using Helio's Ocean (GAH!) and my contract is up in June -- I've been waiting for this day for about 1 year and 350 days. Anyway, this is not a thread to bash Helio's junk or their bad service, it is a thread to get suggestions for what phone I should pick up.
Here are some features I would like (in no particular order):
1- GPS
2- Easy access to gmail (perhaps a simple app that runs instead of needing to hit a website, but not required)
3- WiFi
4- Ability to use the phone as a modem for my laptop
5- WindowsOS (sort-of flexible on this one)
6- Very customizable (one thing I hate about the ocean is that I can do nothing on it without Helio seeing or approving it - apps only allowed that Helio blesses, no home screen customization, etc.)
7- Real QWERTY keyboard -- not an on-screen/touch one
As another thought, the G1 has always been interesting to me. However, it wasn't available in my area code on a fast network. Does anyone have news of when it will go to VZ or some other high speed network in the 83406 area code?
You should take a look at the HTC Touch Pro or similar phones for what you're looking for. You don't mention a particular carrier, but there are both GSM and CDMA versions currently available. If you can hold out a bit, the TP 2 is due out soon - not a major improvement, but some software tweaks. Both meet all of your criteria and have a pretty significant number of tweaks/hacks/alternate ROMS available from various sources.
You might try out the AT&T version since I believe you can use it for 30 days to see if you like it. If you don't like the coverage, you can return it. They don't appear to have HSPA available, though. Check with your local store and maybe they can tell you if it's coming.
ROMs are the guts of the machine. It's the software that's automatically installed when you first turn the phone on and sticks around so that if you ever do a hard reset your phone isn't a blank slate. ROMs are usually "cooked" to improve performance, remove carrier bloatware, enable applications (like GPS), etc. and can dramatically change the performance and behavior of the phone. While there are some out for the CDMA version of the Touch Pro, I believe there's more for the GSM (typically, that's the case since the overwhelming majority of the world uses GSM). By installing a different ROM, you remove the stupid stuff the carriers install and gain access to stuff they block.
I know there's software out there to break the lock on the GPS for VZW phones. Hit the TP forum here and you should find it. The nice thing about AT&T is that since it's GSM, you can buy a fully unlocked version (at a higher cost), drop in your SIM and go. If you travel internationally, that's a big advantage since you can buy a pre-paid SIM from a local carrier and avoid roaming charges (which are ridiculous).