The sun will ~sometimes~ be visible through thin clouds and/or fog. But if the cloud cover is very thick at all, the disc of the sun doesn't always come through.
You also need a clear and sharp horizon to do local apparent noon, and weather conditions will foul that up as well.
Sure there are artificial horizon devices, but they're not very reliable. They work, sort of, but aren't to be relied on unless you've got no choice.
Not sure how it'd work on a moving object like a boat...but if you throw a pointed shadow and mark the point, and then several minutes later see where the mark is, the shadow point will have moved directly to the east.
My guess as to the "sunstone" would be that you'd use two...both in-line and one on each polarization axis, and where the second one went "dark", then they'd be in line with the sun for whatever frequency they were polarizing for.