a) I have already suggested an enhanced contacts app but didn't get much buzz around it. I really think a lot of limitations could be easily bypassed

b) Better backup. E.g., a backup application that saves user data (contacts, call logs, calendar items, etc) in a human readable format and back. This allows for partial error recovery and data merging. This could be scheduled for repeated backups.

c) If at all possible, a call UI replacement. An app could launch over the phone app and allow for slide to answer, slide to hang up, bigger pictures, animated call portraits, all kinds of neat stuff. Don't know how viable it is, but I assume that is an app like espeakcaller can be launched on call and phone speaker switcher can switch speakers then an UI app could launch and send over answer, hang up, etc.

d) Of course, games. I'd kill for a good tower defense game. After I got the new Android I didn't put it down for days.

Also, L2TP couldn't hurt.

ETA: Uuuuu, handwriting recognition.