Search could learn to handle a hierarchy of mailboxes. For example, if you have labels "project1" and "project2", each with sub-labels under them, it doesn't seem possible to make a search in "project1" to go into the sub-labels.
Grep-based search would be good.
When replying to a message, it would be nice if the controls for breaking the window loose of the rest of the application didn't require four or five actions, in different parts of the screen. Here's what I mean. Hit "reply" to a message. If you want to pop that window loose, so that it's actually useable while you run through other messages, you first go to the upper left corner of the editing area, click the drop-down, and hit "Pop out reply". Then go to the upper right of the subwindow that just opened, hold down shift, and click the arrow that points up and to the left. None of it is intuitive, and it's just too much clicking for such a simple action.
It would be nice if the editor wasn't so forgetful about the insertion point. For example, if you're editing some text in a reply, and click on the "..." icon to see the message you're responding to, the insertion point hops to the top of the editing window.
Ability to remove an attachment.
When you delete a message, and you're looking in Trash, have the quick-preview line (i.e., the first few words, shown in the main screen listing all the messages) show the contents of the message you're actually looking at, rather than the first sentence in the most recent e-mail with the same subject. I don't know how many times I've panicked, thinking that I deleted an important e-mail, rather than some formulaic "Catch you tomorrow" or "No problem" message that I had trashed.
I've long ago given up hoping that some organizational capability would come to Gmail that went beyond the pathetic "conversations" mode. Gmail's idea of organization pretty much amounts to this: (1) you either want to list all e-mails by subject all the time, or you want to list them by time all the time; (2) you only rarely want to switch back and forth between those two views; and (3) if you want to list them in any other way, then it's a "search" which delivers limited results, and disappears the instant you navigate away from it.