I got it figured out.
Apparently, I needed the security level of my SRP path rule %Computer\HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\SystemRoot% (aka C:\Windows) to be "Unrestricted".
When using this GPO with my Windows 8.1 machines, I had this rule set to "Basic User" and all was fine. Apparently this needs to be "Unresticted" with Windows 10.
NOTE: I'm not sure why I was able to get my start menu to work periodically when I fiddled with my "Program Files" rule. I suspect it had to do with having to completely disable/reenable the GPO altogether in order to get the start menu back. After which, it usually required at least 2 login/logout attempts to get things going. However, that part is just a guess.