George and Nancy were easily found in 1861, 1871, 1881, and 1891 census records on Ancestry.com, still living in Lincoln County Ontario. In 1861 Nancy is recorded as "Elizabeth" so we should keep this in mind as we search - that this might be her middle name.
In the 1891 Census George is recorded as a widower so we have a timeframe for Nancy's death of between 1881 and 1891.
1861 Lincoln Co.
Elizabeth 39 <--This could be Nancy's middle name
1871 Gainsboro, Lincoln Co.
Abigail 13 <-- the naming of a daughter Abigail makes me think that the Abigail from the 1851 census is even more likely to be a sister to Nancy
1881 Gainsboro, Lincoln Co.
Nancy E. 59 <---further support for the theory that Nancy's middle name is Ellizabeth
1891 Gainsboro, Lincoln Co.
George is a widower, age 74, living with his married daughter "Abby" (Abigail) Pew, her husband and children.
1842 Census of Canada West
I would have liked to search for George and Nancy in the 1842 census (which is a head of household only) but it is not available online for Gainsborough. There is no proof of course that the family wasn't living elsewhere in 1842 but a search of land records in that area could perhaps solve that question.
The Ontario Archives holds microfilmed (but not digitized) Niagara Fonds which consist of the official records of the Niagara District, including Council Minutes, 1842-1853; Assessment and Census Rolls, 1828-1849; Commons School Accounts Ledger; 1842- 1844; Education Register, 1844-1850.
Fonds also includes assessment and other records from several lower tier municipalities including Gainsborough. It would be worthwhile to search for the family in these fonds. We might not find clues pointing to Nancy's father but we might find a great deal more information about Nancy, George, and their children. We should never overlook that as we try to flesh out a family line.
Agricultural Census & Land Records
I decided to search in the Agricultural census for 1851 and 1861 next. If I can find George I will learn his exact land location and from there I can search the Abstract Indexes to Deeds to see all records pertaining to that specific property. Often land was sold or given to relatives, so there could be more clues found there. The Agricultural census exists for Lincoln County 1861 but unfortunately George could not be found. This is another clue, and may indicate that George did not own land.
I decided to do a quick jump to online death records to find Nancy's death. I knew there would not be much new information since parents' names were not recorded that early. It would be unusual for an exact birth location to be recorded but it is always worthwhile looking.
Nancy's death was found on Ancestry as occurring on 28 January 1890 in Gainsborough. Her place of birth was recorded as Ontario, and her age as 69. Her son Calvin E. Fisher was the informant. So nothing new to use as clues for our next step.
Speaking of next steps, it was time for me to decide where to search next. I did want to search for the Abigail Longstreet from the 1851 census and the marriage of George and Nancy but perhaps it was time to branch out to the mention in the original query of "John Longstreet, b New Jersey in 1796 (moved to Ontario)". What would your next steps be?