So, I eventually solved the problem with the help of Elhanan Sharon (@imported_elsharon) and Eyal Sharon.
The issue was a Nios issue and not a Quartus/schematics/vhdl issue.
My Nios design in Qsys had the Nios II Processor component reading instructions from the flash with a flash_instruction_master, but all the other settings had the software booting and running from the on chip memory. We removed the flash_instruction_master bus in Nios II Processor Parameters window -> Caches and Memory Interfaces tab -> Flash Accelerator -> Line Size set to None (was 128 bit before). Then we connected the the instruction_master to the flash.data where the flash_instruction_master was connected before (data_master is also connected there). I ended up having instruction_master and data_master connected to both flash.data and memory.s1 .
After regenerating and recompiling everything things worked.
Worth noting is that we used the system console to debug the Nios operation using the Tcl language. One can view all the registers of the Nios and the memory with that.
Eyar