if I bake an ambient occlusion map is it dependent on the environment’s lighting?
No, AO is not dependent on the lighting situation. You can bake the environment lighting into your textures though if you want to.
I should start on the environment, big objects and lighting vs starting with small props?
I have no idea about your project. In general, you always want to start with the big picture, block it out, and then refine it by adding more and more details to it.
If you have never used Painter before it might be a good idea of course to model some small prop and practice the texturing process with it first.