Hey Ben,
This isn't actually my specialty, so I might get Jano to chime in here too as she's had a lot of experience doing this for the coastal bays and lots of other maps.
I had a look at your attachment and I think you're on the right track. What I'd suggest is that you try to simplify the outline first as GIS files typically have thousands of extraneous points.
Select the outline, go to Object>Path>Simplify, and then you can play with curve precision and angle threshold to get something that works. Make sure you click the Preview box to see how many points are being eliminated, and the new shape - you can even select 100% curve precision and it may still eliminate additional points.
When you go to make it 3D, (Effect>3D>Extrude & Bevel), make the extrude depth 0 pt, and leave Bevel at 'None'. That effect is probably what is taking so long and making it so messy. I'll ask Jano what she does here... but for me to include it in the symbol library, I need you to expand the 3D version (Object>Expand Appearance), and then I'd add the "extrude depth" manually. Let me know if you want tips on how to do that too.
So let me know how it goes!
Cheers,
Tracey