If you go create your textures, always start big, if needed you can always scale your work down afterwards!

A minumum size for creating textures(and not just S3TC textures) is 2048 pixels x 2048 pixels by 2048 DPI. An even better size would be 4096 pixels x 4096 pixels by 4096 DPI. If your texture is not square than always make the longest side at least 2048 or 4096.

Some examples:

Starting with 4096 pixels does give you a better headstart, because it enables you to add incredible small details, but the filesize will skyrocket too unfortunatelly. For the S3TC project i use 2048 myself. But if i would make textures for a new map than i would choose 4096 myself. Its up to you what to choose, as long as you don't go lower than 2048, but if you got the harddrivespace............

The best way to create textures is to make a set of backgrounds first, like all the stones, rocks, woods, metals, walls. In Unreal you can find these textures in general in the Base Group from any Package. Use that same trick, create your Base group first. After creating the Base textures, start adding stuff on top of those Base textures, or carve them out the backgounds, or combine backgrounds (examples).

In this way you will make sure all textures in your map will have the same looks and/or apearence.

A more difficult part is to make your textures tileable, but there is a great Photoshop filter for that, which you can find here: