It is not legal for an employer to discriminate on the basis of sex anywhere in the US (see http://www.eeoc.gov/laws/types/sex.cfm). Exemptions exist where the discrimination is for bona fide occupational qualifications and, irrelevantly, religious reasons.
It is completely legal for a consumer to discriminate on the basis of anything they want to. It is also legal for a business to assist the consumer in that discrimination.
Bona fide occupational qualifications generally only apply to instances in which the BFOQ is considered reasonably necessary to the normal operation of a particular business. Mere customer satisfaction, or lack thereof, is not enough to justify a BFOQ defence, as noted in the cases Diaz v. Pan Am. World Airways, Inc. and Wilson v. Southwest Airlines Co.. Therefore, customer preference for females does not make femininity a BFOQ for the occupation of flight attendant. However, there may be cases in which customer preference is a BFOQ—for example, femininity is reasonably necessary for Playboy Bunnies. Customer preference can "'be taken into account only when it is based on the company's inability to perform the primary function or service it offers,' that is, where sex or sex appeal is itself the dominant service provided."
None of the occupations you mention would, on the face of it, meet the requirements to be BFOQ.
Allowing their customers to express a preference for a specific gender may impact on the capacity for the business to deliver on that preference but it would not generally allow a BFOQ defence if this impacted their hiring policies. A possible exception is if the business catered to that preference exclusively, for example, an all female gym with all female staff but I am not aware that this has ever been tested and if a male personal trainer wanted to take them on he may very well win.
As an aside, there is no BFOQ defence for racial discrimination except for artistic works where the first amendment rights overrule the anti-discrimination laws.