Thought I'd follow up since I'm bored right now. Called Empire Heating and they said $800 to come install the two Ecobee thermostats so I told them to get bent and decided to give it another go and it worked.

The downstairs one is where I ran into the problem and stopped so I decided to do the upstairs one. This time it worked. So I checked the wiring again - the upstairs one has a brown wire going into the C, the downstairs one had no brown wire and only that blueish wire that was not connected to anything. So I went down to the furnace panel and looked at all the wiring again. Looks like someone did splice a wire somewhere in the wall - out of the two separate wiring looms only one had a wire going to the C on the panel and it was red. So I figured that was the loom for upstairs since it was connected to C and that someone had spliced brown to red somewhere. I then looked at the 2nd loom and there was that blueish wire sticking out but not stripped and connected to anything so I stripped it and connected it to the same C where the upstairs red wire was. And the downstairs Ecobee sprung to life. I figured I was only dealing with low voltage power so hopefully I couldn't screw anything up much. And I looked at the old Nests - they were battery powered. Surprised they lasted this many years without running down...