You mention
Several immigration lawyers in the US told me that I have to sue in the district where I reside.
And you ask
how soon after relocating is it possible to file a lawsuit in a federal district court?
You can sue as soon as you can credibly assert that you reside in the new district. If you live in a camper van, this might be somewhat more difficult to establish, but that is probably a topic for a separate question.
However, in order to be naturalized, you must meet the requirements in 8 USC 1427, which says in part that the applicant must have resided
within the State or within the district of the Service in the United States in which the applicant filed the application for at least three months.
This implies that if you move to another state and another USCIS district after submitting your application that you must file another application (there may be a provision for this case that allows you to move after applying, but if so, I haven't found it).