Textures of 512x512 work well, expecially with mipmaps. I use them for my Terrain in my RTS, and it looks great... like the Evil Genius textures!

I think 1024x1024 is far too big, I have always tried to avoid it. I suggest 512x512.