A feature I would like on my iPhone: every single call gets recorded (at a low bitrate to conserve storage space) and stored on the phone for a short period of time. Playback works like the visual voicemail feature.
Update: I've gotten a couple of emails from people saying that this feature is illegal. Which is true in some states (California, Connecticut, Florida, Illinois, Maryland, Massachusetts, Michigan, Montana, Nevada, New Hampshire, Pennsylvania, and Washington). My feeling is that the recording of voice communication is a legacy thing that should go away. If you write me a letter, send me an email, IM me a note, or send a SMS, I get to keep a copy of your correspondence. Why the different standard for a phone call? I believe this difference will eventually go away...after all, it's trivial to record a Skype call.