First of all, the iPhone is not meant to be a feature-rich cellphone. I think Apple wants to provide an intuitive and enjoyable interface that would let all kinds of people use most/all of the features inside it.
Having said that, GPS is a cool feature. The important thing, of course, is to keep in mind the power requirements of a GPS chip. The Texas Instruments Navilink 5.0 chip is a GPS chip for GPS and “Assisted GPS”. I think the Navilink 4.0 is currently used inside N95 phones. Adding the GPS chip would not be too problematic(although the real estate inside a cell phone is awfully small and it depends on a UART of I2C bus to interface with the cellular modem). One has to look at the power requirements though. I have searched for a decent data sheet on the Navilink chip, but all I find are marketing materials that claim “low-power” without specifying how much power the chip consumes(which would affect battery life).
Aside: For those interested, GPS uses Phase Modulation, which is more resistant to additive noise compared to amplitude modulation.