Of course, Nintendo clearly cared about the CPU a lot for marketing purposes (it's in the console's name), but from a purely technological perspective, it is wasteful. Most of the actual compute is done on the RSP anyway. So, getting a much smaller CPU would have been a big corner to cut, that could have saved enough resources to increase the texture cache to a useful resolution like 128x128 or so.
It should be noted, though, that the N64 was designed with multitexturing capabilities, which would have helped with the mushy colors had games actually taken advantage of it (but they didn't, which here again, the Nintendo SDK is to blame for).
How? The texture RAM (TMEM) is in the RSP, not in the CPU.
Anyway, the real problem is that TMEM was not a hardware-managed cache, but a scratchpad RAM fully under the control of the programmer, which meant that the whole texture had to fit under a meagre 4 kB of RAM! It is the same mistake that Sony and IBM later made with the Cell.