I just got an Android phone, and that has GPS built in as well. The free "My Tracks" app in the market tracks speed, distance, time, elevation, min/max grade, and can graph speed and elevation profile. It is tied into Google Maps as well, and reportedly works well for running and cycling.

http://mytracks.appspot.com/