Specific apps are not the issue. Choose a messaging protocol. The Messages app in OS X Mountain Lion (and iChat, which came with earlier versions of OS X) can be used with AIM, Jabber, Google Talk, and Yahoo accounts. There are plenty of Android apps that can also be used with those services.
So, for example, if you both have (or create) AIM names/accounts, you could use Messages/iChat and your friend whatever app he/she wants that supports AIM.