ShadowOfTheColossus

This game has a run page on SDA!

Basics

The PS3 version is based off the PS2 PAL version. The most notable difference is that in the PS2 NTSC version you gain control slightly earlier in time attack, and some colossi behave slightly different at the start of time attack.

Rolling is the fastest method of moving on flat ground (without Agro).
It takes a couple seconds to reach max speed when running, whistling will instantly make you move at max speed when you start running.
During some cutscenes, you still have control of Wander.
Momentum of the colossi can be used to launch Wander in various places.

Jump stab - Jump with triangle, then hold R1 and press square. A jump stab will do the same amount of damage as a fully charged stab; however, it takes much longer to pull the sword out, so jump stabs should primarily be used as final stabs only.
By sheathing the sword (and having the hand icon) then holding R1 and Square when being shaken, you will start charging a stab as soon as possible. This trick is version dependent (verified on PS3 and PS2 PAL).
Sweet spots - places on a sigil where you can stab without being shaken.

You want to whistle at the start of the battle to gain the colossus' attention. Start running, then whistle to get to max speed, and as soon as Wander whistles, start rolling towards the colossus' left leg.
When at the leg, jump and hit the weak spot, then jump and grab on to stab it a second time. Alternatively, you can jump and grab on then do two stabs.
Once the cutscene in which the colossus falls begins, hold diagonal down-left (or jump to the right then hold diagonal down-left if the thigh is in the way). Ideally you want to grab onto the top of the colossus' head, but this is very difficult, so grabbing the chest then climbing up to head may be preferable.
3 full stabs are required, so you want to perform 2 full charge stabs and a jump stab. The safest part of the sigil to stab is the part furthest from the colossus' face.

Face the front right leg and take two steps then take out the bow and do a roll. As soon as the roll is complete, charge an arrow and aim at the right leg and wait for the left leg's paw to come into view and shoot it. As soon as you hit the paw, start running toward the right paw, and Wander will be knocked back by the left leg falling and put into a position where you can jump onto the leg.
Once you jump onto the leg, charge a full jump and you may start running up the leg. If you are really fast, you can jump on the bare patch of skin above the ledge when the colossus shakes his leg, but this is very difficult; alternatively you can climb onto the ledge and wait for the colossus to roar. Immediately upon hearing the roar, jump onto the colossus' back and run for the head.
The sigil on the head has a few sweet spots, the easiest to get is the very top corner of the sigil (Naegleria's youtube video above shows this spot at 4:40), after three full stabs, start running for the rear sigil.
Jumping when running to the back of the colossus will give you a little boost of speed.
When you reach the sigil, you want to do 1 full stab, a 2/3 stab, then a jump stab.

Take two steps forward, take out the bow and do two rolls.
Start shooting the lower sigil with fully charged arrows (you can safely get 5 shots in, but more are possible), this will save you time later when you need to stab it.
Jump into the air when the colossus swings his sword down, as long as you are in the air you are basically immune to that attack if you dodge it. Crouch near the lower symbol on the sword arm and wait.
The sword launch is tricky, at 26.3 seconds if you did everything else right (roughly the point at which Wander is at the same height as the highest bracer on the colossus' right leg), you want to let go of R1, then hold diagonal up-right and jump. If you do it right, you will land on the colossus head. You can also go for the colossus chest, the lower sigil, or the arm.
3's sigils are an absolute nightmare, I don't have much info on how to do them fast.

Jump on agro right at the start, and run towards the colossus' right hind leg. Hold R1 and Up on Agro to stand up, and from this standing position, jump onto the ledge on the leg. Move to the center of the ledge, and wait til the left leg is just about to hit the ground, at that point, do one small jump to get on the ledge, then jump onto the second ledge, then to the tail. It is possible to skip the second ledge and go straight for the tail, but this is tricky.
Once on the tail, charge two jumps and roll towards the weak spot, if you get there fast you can stab it twice before it shakes.
Run onto the head then do 4 full stabs and a jump stab.

Take out the bow and hop just under the gap in the fance, this will let you get some horizontal distance as you fall.
Hold R1 and swim toward the leftmost of the 3 platforms. You will need to get some air, so you can either press triangle to jump out of the water while holding R1, or let go of R1 and take a breath.
When you get to the left platform, jump onto it and charge an arrow to shoot at the bird. Then jump to the middle platform and take your sword out. Jump onto the bird (it should be around 48-49 seconds on the timer if you are fast).
When the fight music stars, let go of R1 for just a moment to be flung a little down the wing. Let go of R1 when it is raising it's wing, and hold R1 as it is lowering it. Letting go of R1 in the right spots will let you be on the right wings sigil as soon as the flapping is done.
Charge a full stab on the sigil and hold R1, there is a chance you can fall off when removing the sword while upside down, so hope that does not happen. When Wander is above the spikes sticking out of the bird's head, let go of R1 to fall and land on the left wing. Ideally you will land on the sigil.
When on the left sigil, charge a full stab and wait for Wander to be above the spikes again to let go of R1, this time aiming for the tail.
Jumping when on the tail is faster than rolling or running.
The hitbox for the tail's sigil is much bigger than the sigil (see Naegleria's video at 21:00).
Do one full charge stab, a 2/3 stab, and a jump stab.

Whistle right at the start to get the colossus' attention, then roll forward and take out the bow. From here you want to roll under the bar (see 34:20 in Naegleria's video) then shoot the colossus' legs. You might want to wait a few seconds for the colossus to climb the wall, since the higher it is when it falls, the longer it will be stunned.
Each sigil takes 2.5 stabs, so do a full stab, half stab, then jump stab on the last sigil.

Explaining the visual cues for the run up to 16 is hard, so just watch at 1:18:10 of Naegleria's video.