How often is "too much". I have water heaters with SSRs in them that flip a few times a second.
You might want to consider a triac.
If you don't know what one is there is a nice description athttp://knol.google.com/k/max-iskram/ele ... 9zgq0e/26#
If you combine this with some sort of optocoupler triac driver w/ built in zero cross detection (Off the top of my head I'd use something like a MOC3020) you should have a simple enough setup.
Edit: Well, I guess I'm not the only one with the triac idea.
Edit 2: Also, if you wanted to make your own zero-crossing detector you could use your triac as a dimmer. This falls into the 'kinda tricky' category, but I would think somewhere online you could find a suitable circuit, the tricky part would be the code. I'm not sure how easy the arduino makes timers and interupts.