As I have stated a few times here, tooting my own horn shamelessly, I am designing an exhibition on paleontology in the Southern California area. I am a designer, not a scientist, but from what I have learned not all the ancient coastlines are under water now. A lot of fossils have been found in Orange County that are up to 100 million years old, and they are mostly marine creatures. In fact, the coast line was around where Riverside is now! Of course, there were no humans here then so no evidence of early man is found.
I guess tectonic uplift on the West Coast explains what you're seeing, but I wonder where the shorelines were within the past few million years, i.e. in the probable timeframe of human evolution. My favorite class in college (and one I actually paid attention in) was Geology and I've always been skeptical about "accepted" doctrines of how, when, and where the human species developed.
Your project sounds very interesting. Where will it be housed?