Triac dimensioning in practice
As high as you can afford. 25A or 40A would be good. No triac you can afford will be as rugged (or efficient) as a relay contact. 
Not a hope. Dissipation will be in the 5W range- read the datasheets and do some calculations. Do not run the triac junction too hot. It won't last long and you need the delta between operating temperature and absolute maximum to absorb the temperature surge from a short or other abuse. 
Use at least a 600V triac, preferably 800V, and consider an MOV. 
Yes, a fast fuse can protect a generously overrated triac from a short circuit. The more demands you place on the fuse, the more expensive and hard-to-find it becomes, and the more likely your customer will replace it with a penny or whatever. 


Keep in mind that triacs are much more likely to fail 'on' than properly rated relays or contactors are.