Your main concerns are paper opacity, grain and suitability for both offset and laser printing.
Opacity: You need high opacity for obvious reasons, to prevent the dark back from showing through on the front. The paper manufacturer will have an opacity specification. I would want 95% or better for this purpose.
Grain: For letterhead, it is very important to specify short grain (grain parallel to the short side of the paper), because letters are folded parallel to the short dimension. This is specified by the manufacturer.
Suitability: Not all offset papers are usable in a laser printer. Heat can cause the paper to scorch, the higher moisture content commonly used for offset paper can make it curl horribly, which not only looks bad, it jams the printer.
Talking to a paper supplier or a reliable printer will help ensure you don't commit these errors. Any one of them will make your client very unhappy.
A third factor that you must consider is the ink. Not so much the ink quantity as the ink type. Inks that are unstable or otherwise damaged by high temperatures will not work for this application. Some types of ink can cause contamination of the imaging drum. This is a trickier one to find out about. Your best bet is to get some recommendations from your print provider (or find out what they use in normal practice) and cross-check with a couple of office laser printer companies.
Xerox has a helpful document online. See the section headed "Preprinted materials" starting on p23.