Auto setup routines such as Audyssey are finding their way onto a lot of new receivers these days. I can't give you any direct experience with them because my receiver does not have any auto setup routine - I always do the calibration manually. However, if you read posts and articles about receivers with auto setup, whether it be YPAO (Yamaha), EZ-Set (H/K), or Audyssey the results are a mixed bag with some saying they worked wonders and others saying they ended up re-doing things manually anyway. All of the auto setup routines set the front speakers to Large which is wrong 99% of the time. So, is it a must-have feature? Not for me but it may be useful nonetheless if you use it as a starting point and then tweak from there.
THX certification guarantees a certain level of performance but also adds features like additional thx surround modes and post-processing that can help to improve the sound. In a way, the THX post-processing is similar to the auto-calibration routines except that it is done on the fly rather than as a one time setup with test tones.
If it were me choosing between the 604 and 703, I would value the THX certification more than the Audyssey auto-setup and would choose the 703. The 7xx series also have pre-outs which would be necessary if you ever choose to add external amplification.