If it has needles and they are brown it is dead
Not necessarily. There are several species of deciduous conifer. Larches/taramacks, Bald Cypress and Dawn Redwood come to mind.
how hard is it to plant a new one (any that is about 2 stories tall, not big)
It depends on what type of tree you're planting. Some are very easy to transplant, others are notoriously difficult. Also, I'd strongly recommend that you NOT plant such a large tree. First, a 2-story (ie. 15-20ft) tree from a nursery is going to cost a bundle, even for a run-of-the-mill cultivar like a river birch or a tulip poplar. Second, a tree that size is going to have a very large rootball (100 gallons?). You're going to need to dig a serious hole to plant it. Third, assuming the tree survives transplanting, its growth over the first couple or three years is going to be pretty slow since it has to re-establish all the roots that were cut when it was dug up. If you plant a small tree (8-12ft) and a large tree (say, 15ft) of the same cultivar at the same time, the smaller tree will usually catch up to the larger tree and surpass it in size within a few years.