After experimenting with a long running average at maxed out FPS and a variety of map sizes, 128 seems to actually be a good size to use if only drawing bits of world with stuff in it. 64 actually did even better in some situations, but significantly worse in others (lots of land, zoomed out).
--- a/hedgewars/uLandTexture.pas Sun Jun 03 18:52:22 2012 -0400
+++ b/hedgewars/uLandTexture.pas Sun Jun 03 22:56:30 2012 -0400
@@ -31,7 +31,7 @@
implementation
uses uConsts, GLunit, uTypes, uVariables, uTextures, uDebug, uRender;
-const TEXSIZE = 256;
+const TEXSIZE = 128;
type TLandRecord = record
shouldUpdate, landAdded: boolean;