is it legal for a business (i.e. Foot Locker, Best Buy) to refuse
service or the sale of its product  to a potential customer based on
any criteria that it chooses? (regardless of how silly)
example #1:  you are 5'9'' tall. a new store opens in your
neighborhood, you decide to go there. there is a sign on the door
saying "if you are under 6' feet tall you are not allowed to shop
here"
example #2: you log into www,shopping.com to buy 'stuff'. they refuse
to sell their products to you because, "your mailing address is a p.o.
box."
please reference law or source with answer.

I too have a APO box. It is really up to the company. The reason
behind this is due to fraud, it is easier to accomplish when you use a
PO box (various aspects).


X

It may also depend on their shipping method, as some delivery
companies may not deliver to a PO Box.

The short answer is "yes," as long as the attempted discrimination
does not run afoul of certain federal laws that protect certain groups
of people against discrimination.  Currently there are no federal laws
protecting persons under six feet in height from discrimination.  Nor
are there laws protecting persons with PO boxes.  So, regardless of
how "silly" the discrimination may seem, it is not illegal unless the
discriminated-against group falls within a protected class.  There are
laws, for example, forbidding discriminatory treatment based on, e.g.,
race, gender, age, physical disabilities, and sexual orientation.  So
Foot Locker could not legally refuse to sell someone shoes because
they are over 50, female and African-American.  Note that these laws
generally only affect PUBLIC places like stores, restaurants, hotels,
apartments, etc.  PRIVATE institutions often times can and do still
legally discriminate based on one or more of the "protected classes." 
These barriers are falling, slowly.  Remember The Citadel and women
cadets?  And there are certainly still private country clubs where
Jews, African-Americans and women are not permitted to join, although
I wager there are fewer now due to threats of litigation.