Finally, an answer -- Thomas Joseph and Margaret Gilligan McCormick are my great-great-grandparents. I received a copy of my great-grandparents marriage license in the mail from the State of New York, and there they were, listed fully by name. I'm especially thrilled to have a last name for Margaret.
My great-grandfather's address at the time was indeed 281 Madison Avenue, Albany, which also solidifies the link I found in the City Directories last month and wrote about here.
I feel like I should write more, but it seems fairly concrete at this point. Both were born in Ireland, so I'll be getting into a phase of research I haven't done before with other branches of my family as these are my nearest immigrant ancestors -- new challenges ahead!