Starting out at 1080i should give you the most temporal, and spatial resolution. You can always downsize it from there.
Depending on the nature of your project (Imported raster footage? Shape layers/vector artwork? etc...), there will probably be some quality loss when you downsize, due to the nature of resampling pixels, but it will be a better option than up-sizing for certain.
As Steve suggests, you should start out with composition settings (note the word 'composition' there, not 'project') that match the largest output size that you might need to output for. Scaling up is nasty compared with scaling down.
I recommend reading the
"Planning your work" section of After Effects Help, which also links to an article from Aharon Rabinowitz about planning your work for different outputs.