2 way switch with Arduino?
Like Gil said, it sounds like what you are calling a two-way switch is actually a three-way switch. These are typically wired like this (but not always, make sure to double check!):

To replace one of the two switches with a relay, you can simply connect a SPDT relay with the load/hot wire (depending on which side you're adding the relay from) to the common contact, and then the two traveler wires to the normally open and normally closed contacts. This effectively takes your existing wiring and directly swaps in a relay -- after all, the relay is literally a switch, just electrically activated instead of manually.
I can't speak to the reliability or lack thereof of a specific model of relay, but a normal power relay is more than adequate for home automation in almost all cases; you don't need anything too fancy. Yes, there will be a mechanical point of failure, but they are typically rated for 100,000+ actuations minimum on a decent relay (like this one from SparkFun, for example) which will take quite some time to reach. Avoid the super cheap relays both for safety and reliability, and you should be fine.