Writing postdoc fellowship before contacting postdoc advisor?
I'd write to the potential advisors with your CV and a summary of the proposal. I don't know what the paper work is for these schemes, but I suspect they require a ~1 page summary or abstract. I'd write that as a token that you've thought about it and arn't just trying it on. You might find thought that the sponsoring institution has processes that must be gone through before they are allowed to sponsor people, and that these have deadlines earlier than the NSF/NIH deadlines.