What Xbox and PS2 uses the most polygons/sec

Jak II and III had a very limited colour palette though (mostly brown and grey). Maybe they just loaded one 8bit palette for each area and used that for all textures?

 

No, each texture has a different palette, and they use a mix of 4 bits and 8 bits textures.
Using a single palette would buy you nothing on the PS2 (just few kb..)

 

But it takes time to load a new palette, right?

 

IIRC it takes 16 GS clock cycles (there is a 64 bytes wide bus devoted to textures on GS) to load a new 256 colors/32 bits palette, a mere nothing.