The T.Rex is more closely 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's existence and the sparrow (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.
Also from this article at Discovery:
"The evolution of the many characteristics of birds –- things like feathers, flight, and wishbones -– has traditionally been a difficult problem for biologists," Mark Norell, chair of the division of paleontology at the American Museum of Natural History and one of the paper's co-authors, added.
"By analyzing fossil evidence from skeletons, eggs, and soft tissue of bird-like dinosaurs and primitive birds, we've learned that birds are living theropod dinosaurs, a group of carnivorous animals that include Velociraptor," Norell continued. "This new work advances our knowledge by providing a powerful example of how developmental changes played a major role in the origin and evolution of birds."
There is also this chart from dino-web (The T.Rex is part of the coelurosauria):
The T.Rex is a part of the coelurosaurian theropod dinosaurs, while the Stegosaurus isn't, which supports the claim that birds and the T.Rex are on 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.
Look at their bone structures:
The bone structures of the sparrow and T.Rex are a lot more similar to one another than to the bone structure of the Stegosaurus. They are both bipedal, upright, have small "hands" and more.
Here is a list of similarities between birds and dinosaurs (from dino-web):
The British palaeontologist Thomas Huxley presented a theory in 1868, which claimed that birds are descended from dinosaurs. His theory stated these reasons for it:
Only dinosaurs had the same sort of ankle joint as birds
Only dinosaurs had the same sort of ilium as birds
Some dinosaurs had the same sort of rear foot as birds with a rear-pointing fourth toe (phalanx)
Advanced dinosaurs had the same sort of build as birds with a short torso, stable hips, long and very flexible neck and long rear limbs
Only dinosaurs and pterosaurs had hollow bones or the air sacks which are connected to a bird-like lung. Pterosaurs are in every other aspect a lot less bird-like than advanced dinosaurs
Some dinosaurs had the same sort of hip as birds (ornithischian dinosaurs).
Also from same source:
The theory of the common ancestor
Because birdlike dinosaurs had only very small collar bones and birds have very large ones, the theory that birds are descended from dinosaurs was rejected. It was belived that, Dinosaurs had the same ancestors as birds, until the following was proven scientifically: there are genes which are suppressed but exist nevertheless. They can be reactivated in situations when they are needed. Chickens, for example, have a suppressed gene which would allow them to develop teeth if they needed them. Scientists transplanted this gene into another part of the chicken's body where it could be reactivated and the chickens developed teeth. Dinosaurs probably had a suppressed gene which allowed them to develop larger collar bones. This is what deinonychus did, which had a collar bone very similar to that of archäopteryx. Deinonychus also had a hand very like that of archaeopteryx. It is therefore very likely that birds are descended from dinosaurs.
The only "major difference" between the sparrow and the T.Rex is their size, but this is not a good measure for relation, one of many examples is the Elephant and Hyrax which are closely related to each other much more than the elephant and giraffe, rhino or hippo, or the hyrax and guinea pigs and rabbits. source1, source2.
Here is a picture of a dino-bird being awesome: