This is basically a conversation about project scope and management. Assuming this is more complex simply because it's a government agency is flawed thinking, though. I can certainly perceive complexity due to expectations or maybe the participants themselves (I've worked with some fed agencies), but that should have zero bearing on addressing the project itself.
But in reference to some of the specifics of how this is different (sensitive data, system load, system attacks, worst-case-scenario) -- this is begging for an iterative project approach as opposed to a waterfall basis. In spite of the fact that these aren't unique issues to government agencies, the context of addressing those issues might be (I have some idea of the technical capacities of our government.) I can accept there may be a learning curve in this project, but believing this project yields unique problems that haven't been dealt with elsewhere -- respectfully, that's just wrong.
If this is all very new to these federal agencies, that simply suggests a smaller initial scope that can grow after multiple iterations. Teams can learn about requirements, refine their APIs, shore up their operation, etc. Not to over-simplify, but this is basic project management.
Again, the context of the government's perview may be different than little-startup-dot-com, but the process of getting from A to B isn't really all that different.
Remember that this has to accommodate the agency in the worst situation. The alternative would be to give separate deadlines for each agency in the memo, but that may be hard to determine from the outside (after all, "what are you going to do, how, and when?" is the first thing he's asking for) and you still have to wait for the last one to have your "Hey, everyone, there's data! Have at!" press conference.