Probably because the textures were just too low resolution. You add bilinear filtering to low-res textures, you get something that looks blurry.
Yeah, the texture memory was anemic. 4KB total. If you had mipmapping on, that ate half leaving you with 2KB which is only enough to fit a single 32x32 pixel texture at 16-bit color.
OMG I thought I was the only one. I was on team Playstation and my friends at the time were all raving about N64 and i was like "Am I the only one that genuinely thinks this looks WORSE?"
Both teams were delusional, it all looked bad on consoles :) one had uncorrected perspective, fixed point math resulting in gaps in geometry and no filtering, the other super low res textures resulting in blurry mess.