In "Halo," the textures looked great (especially up close). I imagine the game must have used small textures. To achieve that kind of effect, what size textures should I use? How do I use small textures without the result of a visible tiling pattern?

As with the polygon thing, that depends of the engine and platform, consoles need smaller textures than PCs. Also, if you use ''many'' polygons, you might have to save on textures, or the other way around.

It sounds like you''re mixing up small res textures vs. small textures.
One thing is having textures that cover a large area in the game in low res, and another thing is having textures at the same res that cover only little bits in a map, thus tiling more often = ends up giving tiling patterns. That''s something you usually don''t do. A decent texture, used at the ingame size it was meant shouldn''t give obvious tiling patterns, if it does, the texture needs a fix.

Halo textures, like in any other game cover about 2x2 or 3x3 ingame-meters, regardless if they''re originally 256x256 or 1024x1024 pixels.

For PC games i''d use 256x256 and 512x512 textures and skins. You have to evaluate what you''re doing, if you''re skinning a simple crate or small map object you can use a 128x128 texture and paste that same on all sides.
UT2 and Unreal2 use up to 1024x1024 skins and textures, thx to DXT compression and mainly smart caching of texture memory and memory usage (same for models btw) ...which is an engine thing again that limites the polycounts and texture sizes you can use.

There are simply no golden numbers for polycounts and resolutions, you have to mix polycounts and resolutions depending of the engine and the way the models and skins are going to be used in the game.
In other words, go ask the engine coder, they always know best what their engine can and can''t do, then there''s a lot of testing to see how it all performs.