It all depends on how closely you're viewing them. We have a bunch of photos shot with a 5D (12MP) printed about four feet tall. They look great from a normal viewing distance. Of course, when you put your face six inches away, you can start to see some digital artifacts (stair stepping, etc.) but that's not a problem.
The maximum necessary resolution is related to the intended viewing distance.
"The standard definition of normal visual acuity (20/20 vision) is the ability to resolve a spatial pattern separated by a visual angle of one minute of arc." From that the maximum resolvable dot size can be calculated for a given viewing distance.
http://www.ndt-ed.org/EducationResources/CommunityCollege/Pe...
http://www.clarkvision.com/imagedetail/eye-resolution.html
(Sidenote: billboards usually printed at around 20-30ppi)