I have used the "Fotek SSR 25DA" for most of the sous vide controllers I have built.
You can find it at dealxtreme or ebay at a very reasonable price.
It needs a low current for switching, meaning that you can connect the Arduino directly to it. Furthermore, being able to handle 25A, I've controlled a 2kW heater with it, and it just got luke warm in spite of only using a piece of aluminium plate for a cooling fin.