Improved 3d terrain definitely has my vote, though I'm more interested in improving the water. That's something that I've wanted since I started playing GK: jumped in the water the first time and thought it was neat to change the sprites purple, but there wasn't anything else. Took almost a year or so for staff to finally add bubbles...
Improved 3d terrain would be great, too: at current, the only non-passable terrain is around the mountains where there are npcs blocking the way. That really doesn't cut it. While I doubt caves and such would work with the current engine - no camera to move - cliffs would, as well as rivers. I hate how the only places that can have water is anywhere with a z <= 0. Could add a basic current implementation too: if the player is in water above z=0, move the player slightly toward an area with a lower average z. To get it really accurate, you'd have to add pathfinding so it follows the course of the river, but I think that would be more than is necessary.
For water, I completely agree with vertex shaders. Not everyone has cards that support them, but probably three quarters or more of gk's players' do. Cards lacking shader support are getting less and less common. The actual shader code would be pretty simple, too. Apply a repeated water surface texture, then add random-ish peaks for waves, and have them diminish as they spread out. Could angle their movement with wind, too. As they spread, stretching the poly faces out further would make it look much more fluid, and would cause the water to appear to lap at the beaches. Adding a pixel shader in conjunction with that to alter the texture slightly based on z and/or speed could add whitecaps and froth for added effect. Adding an enable/disable option in f3 video options would stop it from lagging people with older cards.
Could also add a variation on the 'realtrees' for seabed detailing - seaweed, coral, shells, sunken chests, etc. Would open the door for adding diving later, and then perhaps underwater cities for Zormite
But I'm getting ahead of myself.
I think these improvements would add a ton to gk, and would definitely increase it's appeal. As with crossfire: content only goes so far. New players care about looks more than anything else, and that is what hooks them.