according to my experiments, halving the size of textures speeds up a lot. redistributing the modified original game would be a problem tho.
You shouldn't need to redistribute the entire game. Just supply a PAK with the replacement textures. If I recall correctly, the Quake Engine games use the stuff in the higher numbered PAK files in favour of lower numbered PAK files, using the lower numbered only when it can't find the file it wants in the current PAK.
It might be an idea to have a program that would build a GP2X specific PAK file from an existing Quake 2 install though, if only for reasons of space.
It would also make the whole thing legal. The textures are the property of iD, so resampling and redistributing them would be redistribution of copyrighted material. A program that takes the files you already own and munges them should be legit though.
While this is true, I *doubt* very much that ID would be too down on a PAK file distribution which contains quality reduced versions of the original textures (who'd want to play with them unless they had to?), especially if that distribution had the possibility of squeezing a few more sales out of the now venerable Quake 1. (Recall the number of mods in Quake's heyday which reused copywrited Quake 1 material).
I mean, it's not like a PAK file containing low resolution textures is going to be much use to anyone except Quake 1 players anyway.
As to "this can't be done because people would already have done it", who's to say they haven't?