Should I use the Activity or Message module?
Heartbeat and Activity are both specifically intended for showing user activity (like on Facebook, Twitter, etc.)

Heartbeat is going to be deprecated in favor of Message.  According to the Heartbeat module page:


  This project will be deprecated. The future would be in the module
  Message. It's much smaller and it cannot be compared to heartbeat when
  it comes to features. However the possibilities as API would be the
  same.


Note "the API possibilities are the same."  This means that you will have to write custom code to get Message to do what you want, but as a result you will have more control than the Activity module.

Use the Activity module if you want a solution that works mostly out-of-the-box; use Message if you want to have a highly custom configuration.