RARE used a different technique in Banjo Kazooie (not sure about their other games) that improved the textures in that game.
I think it goes like this. Instead of using 1 stretched texture to cover a surface, they used many smaller textures instead. These textures combined (like puzzle pieces), formed a new texture that had more detail. They probably made one detailed texture originally and broke it apart, then combined it's parts on the surface. I think that's how they got past the small texture cache or something. And because the cart is so much faster than a CD, it loads all those different little textures immediately.
That's why in this game, you can see some large surfaces having very good textures, some of the best examples is in the room where the Treasure Trove Cove entrance is located.
Attachment 10815
Attachment 10814
Like i said, i think this was the method. Maybe i'm wrong so someone could correct me. Either way, B-K had some amazing texturing in the whole game and it's probably the best looking N64 game because it hits the nail in all aspects, textures, frame rate, geometry, view distance, sharpness, lack of fog, etc. Unfortunately, very few games come close to this and even RARE missed the mark with later entries, messing with the frame rate mostly.
Also yeah, B-K was a 16 MB cart, not even a 32 one that became a standard in later N64 big releases and still has better textures than most of them.