Having spent many years working on this problem in the US market, here's my two cents ...
There are tens of millions of mainstream handsets on the market that contain GPS, including virtually all phones sold by Sprint and Verizon in the past few years and most new AT&T phones going forward. However, location is typically locked down and requires a relationship with the carrier to access the handset location APIs. For location privacy and business reasons, making a deal with a carrier for a location-enabled application is often a multi-year process.
The other possibility is to target smart phones such as the Nokia N95, iPhone, Blackberry, Windows Mobile, or Android that provide more open access to location. This is a good audience of early adopters with high data usage, but it's a very small percentage of total phones on the market.
Handsets using carrier-assisted GPS will typically have better performance than smartphones. The 'autonomous GPS' in most smart phones takes a long time to get an initial fix and is less accurate than carrier assisted, or aGPS handsets, which utilize cell towers on the network to enhance performance. Note: The new iPhone will combine GPS, Wi-fi, and cell tower location and so should be fairly fast and accurate.
One means by which developers can gain access to location across multiple carriers is through WHERE http://developer.where.com (caveat: i work there).
I'm working on a white paper covering all of this in more detail. If you're interested in getting a preview copy, let me know.