I think the talent gap between Byrne and Harrison/Franz/Weymouth is wider than the gap between Lennon and McCartney and (G.) Harrison, but not as wide as the gap between Simon and Garfunkel.
I don’t how Talking Heads collaborated other than Byrne handling the lyrics. But I think Tina Weymouth is an exceptional bass player.
The thing is, the OP is asking to compare two people who don’t necessarily practice the same art. Byrne’s conceptual talents are far-reaching, and it may not even be fair to compare the two as musicians since music is only one of Byrne’s interests. But Byrne’s non-musical works are of no interest to me, so comparing them by the metrics that interest me (songwriting prowess, singing and performing ability, and so on), Costello well outstrips Byrne.
I’m going to see Byrne on Sept. 23. I’ll tell you then.