I find I do much better with an immortal or two in the mix. Make an Immortal while the robo support bay is building and then push with it while you wait for colossi to spawn. You may actually be able to win right off this push if you have enough stalkers and one immortal, because you can crush his army and set him back, pull back and get a couple colossi, then go back in for the kill after range is done (so actually, you wont win off the push, but you'll set him far enough back that he falls when the next attack comes. Key thing is don't lose your army! Hit him hard and pull back while he's reeling, don't go in for the kill right away). Try and always keep one or two immortals in your unit mix, they will absolutely destroy stalkers and three immortals can take down a colossus in I think two volleys. Also, use guardian shield, makes a huge difference in battles.
And yeah, phoenix are garbage for helping the colossus battle. They do bonus damage to light, but barely even dent armored guys. They can kill workers, overlords, uncharged void rays and medivacs, and thats about it. Great for harassment, terrible for actual support units unless they're lifting tanks or immortals to buy your ground army some time.