I'm the runner of the PC version in that thread and I very much feel a TAS of this game would be very entertaining just through the experience of running it and optimizing the game myself. There's a whole slew of tricks and glitches to exploit. Some I think will surprise you an eliminate most of the backtracking that seems to invoke some of the hate this game garnered.
Water boosting - Double tapping forward just under the surface of water and jumping out to give Turok his increased speed and you can hold it for as long as possible until you enter another portal then it disappears. There are different levels of speed depending on how you do the double tap and quick jump out. so maximum speed is essential, but that's easy to do. It can be used anytime there is water so levels 1, 2 and 4 have huge time saving potential. It also works on the fans in level 6 - Primagens Lightship, although it appears the speed increase is slightly less, but it still enables some excellent skips and long periods of increased speed which my next upload on my youtube page will show.
Overhead item jump - items floating in the air above your head can be gotten no matter high high above your head they are with a certain type of jump. Stand underneath the item, look up at it (might not actually be needed?) jump and turn slightly in the air. I believe it really helps to push forward slightly during the turn. Several items throughout the game can be got like this with pretty much no limit on height for what can be collected. You can see some huge skips from this trick including collecting the level 2 P-key from the first place you see it, instead of taking the intended path.
Damage boosting - This one has small gains in the standard scheme of things and not all enemies give you a decent push. Except for the mantids and some enemies in level 6. One boost in the Hive which saves several minutes, and another in the Lightship saves about a minute. You can avoid the backtrack to the Hive of the manitids to get the Primagen key with a damage boost from the mantid at the eye of truth bridge leading up to the Key. In fact in this run you don't need to collect the eye of truth at all. You see the bridges are still there, but invisible, but only a small portion is missing at the beginning which is why you fall. A damage boost will clear this gap and land Turok safely on the rest of the bridge even though it's invisible. For the other damage boost you have to get a damage boost from a wheel bot in The Primagens lightship to clear the gap leading up to the last switch which needs to be pressed to bring down one of the four force fields surrounding the last P-key.
The level order for the first 3 levels should go: 1, 3, 2.
Level 3 before 2 grants you the souls talisman which grants you some water boost opportunities early in level 2 which contain soul water, and also a glitch/trick which I was too late in finding out unfortunately in my run, which involves jumping into the river and jumping out and through the raised bridge. The bridge somehow doesn't block and you go straight through it, so no need to do a 20 second or so detour to shoot the switch to lower the bridge.
For the next levels it's pretty hard to see whether level 4 before 5, or vice versa is faster. There's probably not much in it, but some proper testing will need to be done. For my run I did level 4, then 5. Reason for that was you get the torpedo launcher in level 4 which speeds up the water sections in level 5. But on the other hand doing level 5 first would mean you'd have the whispers talisman so you can clean up the level 4 P-key and the rest of the level in one fell swoop.
If it's feasible at this time I would say Tasing the PC game is the better option. Strafing for one is smoother and faster and closer in style to more modern first person shooters. The N64 version strafing was really bad for some reason and it may prevent some really cool skips due to the a possible loss of speed.
Anyone interested in TASing this game I strongly suggest watching my WIP of the PC game which uses many segments for best optimal play as I feel it provides a strong backbone on which to plan a TAS just from the sheer number of tricks me and Squeebles on the SDA thread found. My latest run is the Hive so if you want to start from Port of Adia, it's just a little further down the list. I'm currently running/optimizing the Lightship
http://www.youtube.com/user/Giganotabehemoth87?feature=mhee
Any questions I'd be glad to help answer.