I'm working on a project with very limited texture space for a large object. I can have one 1024 map and one 512. One needs to be diffuse and the other for normals. In the Infinity Blade talk at GDC, they said that they used large normal maps and small diffuse maps for their textures to maximize the detail for a small…
First thing that comes to mind for solving this sort of thing is using modularity of some sort. As for the reasoning behind using bigger normal maps than diffuse could be that the surfaces become more dynamic in different lighting conditions, in turn building on top of existing diffuse detail.
That really isn't that tight of a budget. :P The question of which for what comes down to what you are making. If you have what are essentially large blocks of similar colors, or smooth gradations, you can get away with smaller diffuse maps and letting the bilinear filtering work for you, while getting a nicely detailed…