The T.Rex is closer related to birds than to Stegosaurus.
The comic shows it in 3 different aspects:
From the T.Rex Wiki page, it lived during:
Fossils are found in a variety of rock formations dating to the Maastrichtian age of the upper Cretaceous Period, 67 to 65.5 million years ago.
While the Stegosaurus lived:
They lived during the Late Jurassic period (Kimmeridgian to early Tithonian), some 155 to 150 million years ago in what is now western North America.
Which means that the time period between the T.Rex and the Stego (83 million years) is longer than the time period between the T.Rex existence and the sparrow's (65.5 million years)
The Wiki article for Origin of Birds says:
most researchers now support the view that birds are a group of theropod dinosaurs that evolved during the Mesozoic Era.
The T.Rex is a part of the theropod dinosaurs, while the Stegosaurus isn't, which supports the claim that birds and the T.Rex have a common phylogenetic branch, later than the T.Rex and Stegosaurus.
There is the article linked to by explain XKCD which says that (as the question quotes).
There is also this article on discovery which states:
Modern birds retain the physical characteristics of baby dinosaurs, according to a new Nature study that found birds are even more closely related to dinos than previously thought.
Depending on the non-avian dinosaur and bird compared, that might be hard to believe. A toothy, angry reconstruction of Tyrannosaurus rex, for example, on first glance looks little like a common garden blue jay. Also, look at the bone structure yourself.
The bone structure of the sparrow and T.Rex is a lot more similar than the T.Rex and Stegosaurus. They are both bipedal, upright, have small "hands" and more.
The only "major difference" between the sparrow and the T.Rex is their size, but this is not a good masure for relation, one of many examples is the Elephant and Hyrax which are closly related to each other much more than the elephant and giraffe ,rhino or hippo, or the hyrex and guine pigs and rabbits. source1, source2.
Here is a picture of a dino-bird being awesome: