Turned off iCloud, but still deleted my photos from all devices
The problem is you misunderstand how iCloud Photo Library works. It syncs your photos so that all devices match at all times. Therefore, when you told it to delete your photos on your old phone, you were telling it to delete them everywhere. You can restore them from the Recently Deleted folder on your Photos app and/or www.iCloud.com.