naturally someone has to program that flash the first time. And each board design determines how that actually happens, sometimes the part is programmed before being soldered down, sometimes there is a backdoor a connector you can program through, etc. Sometimes not. Sometimes the processor or other hardware on the board has some other kind of bootloader that you can use to program that normal boot flash, etc.
NOR or NAND isnt usually much of a difference, my biggest problem with the newer flashes is worrying about read-disturb. Flash reading is faster than writing and a lot of the effort is or at least needs to be in write speed and density and cost, so I would assume that is where the efforts are and not so much read speed vs write speed. If you have a read speed problem, then just copy the bootloader to ram as soon as you can and run from there, stay off the prom after that.