Bass? Metal Man? Roll? There's quite a large list of possible classic 3D styled versions of classic characters, as the only low-poly ones are from the Legends designs.
I like to make models in my free time. I also make weird games, too.
You could merge multiple textures into what looks like a single one side-by-side for the blurry-ish areas (this is something Rare did a lot in their N64 games)
For example, you could have four 32x32 textures arranged in a square to make a 64x64 one that fits the limitations.
UV mapping is important too, as you can optimize some space by making half a texture talk up the required space, and just mirror it for the other side.
I'm sorta tired, as I just woke up, but it's hard for me to explain things right now.
I like to make models in my free time. I also make weird games, too.