Track recording i think it should be a must, possibly in gpx format, with exporting allowed, it should be also quite easy to implement, it's present pretty much in every gps application.
Even more important is the feature to import tracks (again in gpx or kml format, the most common), and to show such tracks as an overlay over the displayed map.
Waypoints creation + import/export of waipoint it's also a much needed feature.