In my Halloween layout build thread, I did my first ever foray into foam building. It was a lot of fun. For the layers that got stacked, I didn't both stripping off anything. Use Glidden Gripper (it's a primer) to stack the foam pieces. Other adhesives don't work because they need air to set up.
For what you are doing I would make the pieces removable only because they would be easier to decorate then reinstall.
Lots of options for texturing and surface cutting. A hot knife is great because it's flexible and doesn't make a mess. Other tools are utility knives, razor blades, hacksaw blades used by hand, rasp, and my personal favorite, a pumice stone. (Yes the kind you can use to scrub callouses off your feet.)
Painting can be anything, once you get a good foam compatible primer down. Since you are doing a water's edge, I high recommend you keep watching those you tube videos about shading layers of paint.
