How to switch 1000w AC load with minimal heat?
Alternative would be a over-specced SSR, based on the load, I presume your using something like a 10 to 25A one, so try a 60 or 80A one, the device is made to run at X temperature for that rating, and half the current means quarter the heating over the switch. so a really big SSR will run with a 10A load at a much cooler temperature. 

Edit: Based on his new edit, Clearer what the issue is now, change out your opto-triac for a MOC3041, that way it will not trigger until it crosses through zero again, instead of monitoring it with the micro

Edit 2: Also the above still applies, a larger triac will reduce the dissipation, e.g. 30A triac datasheet in the same package as what your currently using would have half the dissipation.