How can I recover photos from Photo Stream to my computer?
As this is tagged photo-stream I presume that you 'backed up' to Photo Stream. You can recover the photos from your Photo Stream by opening the Photo Stream on your computer.

~/Library/Application Support/iLifeAssetManagement/assets/sub


Inside this folder are all the photos from your Photo Stream. Copy them to your new phone.