Just a quick note, did some reading on Triacs last night from this ST micro app note: http://www.mouser.com/catalog/specsheets/stevalill004v1.pdf
Determined that with a BTA16-600CW3G Triac, I can run it at up to around 10A with 38mm heatsink (4.4C/W at 35C ambient). I bought some 34mm TO-220 heatsinks from eBay, I'll do some experiments to see if it can handle the ~10W load that the Triac will dissipate at 10A. May need to drop from 1200W power control down to 1000W if not.
Looks like the relay will be this part: http://www.digikey.com/product-search/en?keywords=PB1267-ND
$2.02 for single unit price, can handle 250V/16A (4000VA switching), and has a similar sized footprint as the Songle 10A cheapo relay that I was initially planning.