Tortoise is one of the first post-rock bands I ever really listened to, and I wouldn't say Godspeed is any less challenging than Tortoise. I mean, the OP already said that they enjoyed that, and in a way it seems like going back towards something like Sonic Youth or REM or The Pixies would be moving in a completely different direction.
If they're listening to Godspeed, I just assume they're already somewhat accustomed to the post-rock structure and songs that can kind of try an uninitiated listener's patience.
That being said, TNT, as great as it is, is probably not the album to start with. But Standards, Millions Now Living Will Never Die, or It's All Around You would, I think be good albums to start with when it comes to Tortoise, despite not being on the same level as TNT. In my view it's a natural progression, at least it was with me, though I was personally never a big Godspeed fan. Hell, I'd recommend Tortoise before I recommended the early Mogwai albums, as much as I love them.