I grew up on AOL Instant Messaging and now AIM and even now decades since I stopped using AOL I still use AIM as its what the majority of my friends still use. They have a decent iPhone client that will do push notifications, as well as a Blackberry client. There are lots of IM aggregaters too for the iPhone that I believe do push as well.