After writing this up, there shouldn't be any spoilers for those who are doing the scenario for the first few times.
Shrines:
Order: Emerald->Blue->Ruby->Obsidian (fly up and kill yourself at Obsidian to return to entrance).
Use the Sands of Time as soon as you get them. If you get a Shrine clear before Ruby and no Portal clears, just reset. If you get one at Ruby or later, save til you finish the Obsidian Shrine and you get a random buff instead.
Kill the rare Magnataurs outside each shrine before you kill the closest boss. Also, one circles around the temple.
Check each shrine for a Time Chest, only 1 spawns in each shrine per run:
Emerald has 2: (63.71,73.53 in the water) and (65.77,73.34).
Blue has 2: (56.54,68.72) and (54.42, 65.03 on the platform).
Ruby has 2: (48.76, 49.44) and (45.11,47.42).
Obsidian has 4: group of 3 at (66.01, 26.43) and 1 at (33.31,36.41 inside, which is not worth getting).
Portals:
Order: Hyjal->Well of Eternity->Andorhal->Strat
Culling of Stratholme and the Battle of Andorhal take the longest and should be skipped if possible (must be skipped if you want to do it with current buffs).
Otherwise, there are time chests in at least one of two locations in each zone:
Culling has 2: (61.05,28.49 ground floor) and (44.16,43.77).
Andorhal has 2: (39.57, 68.15) and (47.47, 68.28).
Mount Hyjal has 2: (33.85, 98.27) and (36.6,96.18)
Well of Eternity has 2: (26.62,37.23 second zone) and one along the water to the right in the first zone (70, 67).
One final note for the Well of Eternity specifically, you can stick to the right after running in, you can avoid almost all adds except the first doomguard. Assuming you mount up right after and continue moving, you should be able to avoid the abyssals. If you're going to aggro something, aggro a doomguard because they do the least damage and have the lowest amount of health.
Overall: If you just get a lot of time increases and damage reductions, you're not going to finish on time.
You're best ones are Portal clears and damage increases.
If you're lucky, you'll get 2 sands from each rare, 1 sand from each boss, and 2-3 sands from each time chest (with an average of 3-4 per run).
For myself: I received the Portal clears for Strat and Andorhal, had 4 damage increases, 1 damage reduction, 300 seconds stolen (didn't use any).
So if you have useful tips you can post it here.