If I purchase a domain, I'm usually required to enter an address. Usually, the address can be accessed publicly by any sort of WHOIS lookup. I'm uncomfortable publishing my real home address; what do people usually do? Lie? Purchase a P.O box?
Not disclosing your personal contact information is a common concern, since as you state, it's otherwise publicly available at domain registrars, and any site that implements WHOIS lookups.
These will prevent the public from seeing your home address and contact information (including email address), while staying within ICANN guidelines since the registrar will act as the administrative contact and forward important emails regarding the domain to you.
It's not a wise choice to provide false information during domain registrations because if there's ever a challenge for your domain name (UDRP) you'll lose the decision due to violating their terms requiring that all registrants provide valid information at the time of registration, as well as maintaining valid contact information throughout ownership.
Additionally, the registrar may seize, or even delete the domain, if notices from them are not properly delivered. For example, some registrars confirm if addresses are valid on a periodic basis, and request that you update them if not. So if you don't receive these notices, you might have a serious issue with your domain...
You can use a P.O. Box, however, that's more expensive on a monthly basis than just adding a privacy option for a year during registration and renewals (and all your other contact info will be blocked too).
Tip: If you do opt for the privacy option during registration, look for discount "codes" so they're more affordable for the first year.
The simplest solution is to choose a registrar that respects your desire for privacy. I use Gandi.net though there are most certainly others. I don't work for them or have any financial incentive to recommend them, I am just a happy customer.
I'll make this a community wiki and please add any registrars that also do private registration by default.