I have given up on Mail. Here are the programs I've tried as an alternative, with comments. All work fine with gmail.
Airmail (App Store): It uses the same mimalist design that Sparrow did. If you liked Sparrow, you'll like Airmail and will have an easy learning curve. It will only sort mail by date (sent or received), but it has a good search function and a nifty feature which will show you all emails from one sender. It supports multiple accounts and multiple aliases. For me, it's been my program of choice. One hint: I find using the "classic" look better than the "modern," because in "modern" the little icons that allow me to limit the inbox to new, starred, attachments, etc. are grey on black and harder to see.
Inky (their website): Inky sorts mail in the cloud according to rules, with categories like "social," "purchases," "subscriptions," "personal" etc. The program will learn how you want those rules applied as you use it. It is more power-user oriented: it'll sort mail by date, sender, subject, etc. While I llike Inky's approach and found its mail sorting useful, it has some serious problems. It supports multiple accounts but does not support aliases. Its cloud causes lags when sorting, deleting or receiving email, and even when composing email. Its GUI looks like a artsy version of the classic email program, with options to make it look like Mail or Postbox/Thunderbird. I'd say they have a way to go, but if they can work the kinks out it'll be a good program.
Unibox (App Store): Unibox will sort email only by sender. It supports aliases and multiple accounts. It has a very simple, slick interface that works flawlessly. I found it challenging because I have three gmail accounts and am on a few group email lists: individual responses to a group email get sorted by the sender, not by the email thread. The default view is a unified inbox, and moving to each account's individual inbox involves going into the gmail folder tree. If you have a small number of emails or get emails from individuals only, this might work for you.
Postbox (their website): To me, Postbox is the classic power-user email client. It'll sort the email however you want, it supports multiple accounts and aliases, it will let you under the hood to tweak just about anything. It is based on Thunderbird's engine, which means it hogs CPU resources. My wife loves it because of its flexibility. So far, she's reporting no gmail syncing issues.
Mail Pilot (App Store, I believe): I tried Mail Pilot's beta. If you want a program that looks and feels like Maverick Mail and gives you a deadline approach to email sorting, Mail Pilot may be a good choice.
For me, Airmail comes the closest to the ideal email client, but you may feel differently. You could try several, depending on how much you want to spend to experiment. Airmail is inexpensive, Inky is free. Unibox and Postbox are $10 each, I believe.