The attached patch should fix this. The problem is that when the frame is made, the current value of ns-use-native-fullscreen is copied to a variable and that's only reset when the frame goes from fullscreen to windowed. I believe the original intent was to ensure that the mode could not change while the window was fullscreen already.
This resets the value of fs_is_native if the frame is not already fullscreen, which allows it to respect the value at the time of the first fullscreen.
Without this, the only way to get the behavior that Sean is expecting is to set ns-use-native-fullscreen in early-init, which should not be necessary.
0001-src-nsterm.m-EmacsView-toggleFullScreen-Reset-fs_is_.patch