Sorry RR, I navigated a 44' Luders yawl from Annapolis to Bermuda every year for four years and seldom had a problem getting 5-mile or better fixes.
Before the Navy went all "nuc", I also navigated two Guppy (converted WWII Fleet Boat) submarines in the Atlantic and the Pacific and got equally satisfactory results. Except for adverse weather conditions "conventional" submarine stability on the surface was excellent. The first ship I served on after being converted to a Surface Warfare Officer was a WWII design DE, displacing about 1800 tons and she was not as stable a platform as the Guppy boats. We still never had a problem finding and holding the horizon and getting good fixes. The only times I can recall, in nearly 30 years at sea, when there was ever a problem getting a stable horizon was due to poor weather (fog, rain, clouds, heavy seas, etc.). Unless you're in a serious storm, standing on a rolling, pitching deck and steadying yourself with a sextant or a pair of binoculars in your hand is not terribly difficult for an experienced sailor.
I haven't bothered to try any of the attempted "real" (celestial) navigation MODs in either SH3 or SH4. I just operate as if it needed to be done; being sure to be on the surface for an hour or so before sunrise, after sunset and for a few minutes around noon. It can be carefully integrated into a routine schedule for trim dives, surface searching and hydrophone searching. Boring? Well, sure, I guess. The real world of war at sea was once described as interminable boredom punctuated by bursts of panic.
You're very accurate in your observations about the night sky in today's world. I grew up in the Lake Superior highlands and discovered the real night sky (without any "light pollution" from anywhere) when I was around six years old. I still go up there to rediscover it as often as possible.