Sparrow for iPhone was released yesterday and by all counts (including my own) it's great.
The one complaint that some people seem to have is that it doesn't support Push Email. I've rarely used the Push Email feature in the iPhone mail client due to the major suckage of power from the battery.
However, that doesn't mean that I don't want to be notified of new email.
I use Google Apps Mail (Gmail with my own domain name) and the connection to that service is plain ol' IMAP. Built into the technical standard for IMAP is something called IMAP IDLE mode.
Basically, if your mail client supports this feature of IMAP, you'll receive notifications when you have new mail. Of course, the iPhone Mail app doesn't offer this (and neither does Sparrow) but that's OK: for a couple of bucks, you can purchase a third-party app that can do this for you.
The primary reason for going this route is battery life - IMAP IDLE immediately notifies me of new mail, but it doesn't automatically push all new mail to my phone and drain my battery in the process. This is also good to conserve bandwdith, especially now that our "unlimited" data plans aren't so unlimited anymore.
I've used a ton of these apps, but I'll shortcut the pros and cons of all of them and jump right to the winner here:
The best app for email notifications (so far) is eNotify.
It has lots of options for each email account including things like"Quiet Time" so that you can leave your phone on at night and not be woken by the alerts as well as some advanced features I've not found in any other app of it's kind.
For example, you can have it solely notify you of new mail from a particular person like, say, a client or your spouse and no one else. Or, you can have it monitor a particular folder to tell you when your favorite newsletter arrives. Stuff like that.
Cons: the app developer doesn't understand the "less is more" theory of development. The app is absolutely HUGE by iPhone standards (11 MB) since it includes a bazillion sound files that you can select for audible notifications, and in the last update, the app now includes some kind of VOIP client? (I have no idea. And there's little or no documentation. Just turn it off.)
Oh - and the icon is ugly as sin, but you get used to it. (I won't even include it in this post. I have standards, after all.) ;)