Add a search tool: Other than the option to use Google or Yahoo in the iPhone's version of Safari, search is simply missing from the iPhone. If you can't quite remember which email message had your friend's phone number in it or which week in October you have a dentist's appointment or the name of the rep for a company you work with, you'll have to spend some time flicking away. The same holds true for Notes. And forget about doing an iPhone-wide search. Either each application need its own search interface or Apple should add a dedicated Spotlight-esque application to the home screen.
Enable multiple selection: Most Mac and Windows users are so accustomed to the ability to select multiple items that it's become second nature. Unfortunately, no such capability exists on the iPhone. While this might be a minor annoyance when it comes to Notes or SMS conversations, it becomes of critical importance in apps like Mail, when you need to deal with the occasional onslaught of spam messages. At best, you can swipe and delete each email, two gestures per deletion. Some capability for batch-deleting or -editing - not just in Mail, but in other apps, as well - would save time and sanity.
Bring landscape mode to more applications: Typing on the iPhone's keyboard is among the device's surprising pleasures. But that doesn't mean there aren't potential improvements to be made. In Safari, you can turn the iPhone sideways to access a wider keyboard for easier typing. So why not make this orientation available in other text-heavy applications, such as Notes and Mail? Why not go the whole hog and make it available whenever you summon the keyboard? Hardcore iPhone typists everywhere will thank you, Apple.
Establish some interface consistency: The iPhone manages to maintain some degree of consistency in its interface, but there are times when it can throw you for a loop. Why, for example, can you not swipe Notes, Contacts or Voicemail messages to delete them? And why does the Edit button appear in the bottom left corner of Safari's bookmarks, but the top right corner the rest of the time? Learning different muscle memories for different applications is to be expected, but consistency is the watchword of good design. You never want to have think about where a control is twice.
Overall, we love Mail - in many ways, it's the best mobile email client any of us has used. But there's the rub: because it's so good in so many ways, the places it goes wrong are glaringly, frustratingly, head-slappingly obvious. In fact, of all the built-in applications, Mail is the one that generated the most feature/improvement requests in our informal, internal poll.
Create a unified inbox: A unified inbox - like the one found in Mac OS X's Mail program - would ease the tap-heavy task of checking new messages across multiple email accounts. It takes three taps to go into an account, grab a mailbox on that account, and open the first message, and three taps to get back out. Multiply that across four or five email accounts, and you've got a lot of tapping ahead of you that would be entirely eliminated if Apple added a single unified inbox.