I've had best luck carving rigid urethane foams. It makes a big mess, and the dust sticks to everything (think static cling on steroids). But it carves cleaner than styrene-based foam, and you don't get tear-out like beadboard gives you. The denser foams are easier to work with, more structural, and hold better detail, but the lighter ones are cheaper, so you need to balance these factors based on the individual project.
You can coat urethane with epoxy, but it's expensive, messy and difficult to clean up. If you're trying to make a rigid shell you're peeling off the foam (like a boat or something) then you can use glass or other fibers to reinforce it. But if you're just making props out of foam and you want to firm up the surface so you can paint it, an acrylic emulsion works fine, and it's a lot easier to deal with as well as being cheaper. I've used this stuff successfully: Steve's Foam Coat