My frustration lead to inquiring with some skilled members of the Galaxy Nexus community, including @Ziyan, @freshgiammi, and @aosp. They have indicated that 4.4-based ROMs seem to be afflicted with this problem, but that it might also be tied to the kernel being used.
I have two phones; one running stock 4.3 (Sprint) and another running CM11 M8 (also Sprint).
I have Google Maps (and all other software, including Google Play and Play Services) completely updated. The screen brightness is set to auto. I've tested using Navigation initiated by WiFi, and then disabling the cellular radio (to ensure that the overheating is not being caused by radio activity.) I checked OS Monitor by switching through recent apps mid-testing; this gave me a snapshot of system temperatures and a glimpse of CPU usage.
- Stock - Worked perfectly. Navigation, at any time of day, seems to work wonderfully. I do notice that the phone does get warm, and using OS Monitor, can confirm that it reaches 47 degrees C (and holds), never exceeding it. The phone continues to charge without issue. OS Monitor cited CPU usage of 29% at the highest (note that this does not indicate that Maps never used more than 29%, just that 29% was the most I witnessed while checking 15-20 times over the course of 10 miles.)
- CM11 - Phone overheats within minutes of starting Navigation, reaching temperatures of 53 degrees C--and as high as 58 degrees C. The phone stops charging as soon as the system registers an "overheated" state. OS Monitor's highest CPU usage was 52%, which is almost double as high as I saw under the stock firmware.
So far, it appears when my phone has been asleep or idle, it's operating at 29-35 degrees C; so it's nearly doubling it's temperature when Navigating. Additionally, this behavior occurs at night, when the sun (and warmer temperatures) are no longer a factor, which seems to rule out the idea that the environment is a major contributor.
I have a good friend who also as a Sprint Galaxy Nexus running CM11; he is a Waze user, and is experiencing the same issue.
Is this a known issue/problem with 4.4-based ROMs? This has been speculated in other threads, but perhaps a more definite answer/explanation is warranted?
Might this be related to the kernel in use, and the thermal throttling limits? What would be the best method of testing such?
What tests or other steps should I take to gather more information or test more factors?
EDIT 1: At @aosp 's recommendation, I'm looking for thermal throttling capabilities via the Kernel Tuner (2014 beta) application. The "Thermal" button is available, but grayed out. Is it safe to assume that means the kernel I'm using has no thermal throttling capabilities, which would (probably) explain how the Galaxy Nexus seems to be able to work itself into an overheated state?