Where are you starting? If you're in Florida I'd just head off to Vancouver. The toughest and most sustained headwinds (SE) I've ever experienced was going eastward across Colorado and Kansas - Grand Junction to Wichita. I really wished I had been going in the opposite direction.
In Nebraska and southern Wyoming I have had hard S and W winds. In northern Wyoming I have crossed the state E to W without any appreciable headwinds. In Oregon and Washington, however, you will probably get westerly winds up the river valleys so starting in Vancouver would probably get you tailwinds for a while.
East of the Mississippi the wind direction is dictated by the fronts coming through.
If possible bicycle as little as you can in Mississippi, Alabama and Louisiana. Bad roads and bad food abound although the people are very nice and courteous. Western Georgia is somewhat better and the KATY Trail across Missouri is a real treat - the longest bicycle trail in the country.