Mmmm, well, to start with, Mail, Thunderbird, and Entourage are all sensible alternatives. I guess the other major option is Eudora (which apparently goes open source this year), although most Mac users use one of the first three. Outlook for Mac really shouldn't be an option unless you have some specific reason to be using it.
It's hard to answer the question of which of those first three to use without knowing at least something about what you want.
All three will support GMail roughly equally well.
The biggest difference between the three is that Mail is a mail-only program (that integrates with iCal and Address Book) as is T-bird, whereas Entourage is an integrated apps that has PIM functionality plus some basic project file management tools (project center).
Mail and Entourage will be fairly easy to sync with PDAs and so on -- T-Bird will probably leave you on your own for that.
T-Bird will look and feel pretty much like a Mac version of T-Bird. So if you're used to it already, it will feel comfortable, much the way Firefox is great when you're browsing on more than one kind of computer.
Other than that, honestly, all three function pretty similarly. They even look fairly similar. I didn't find anything to be a major challenge in moving from Outlook on PCs to Mail on Macs.
I personally would start out with Mail, which is what I use.
