You also might be able to do it via CalDAV -- not sure if those get synched to the iPhone, but if they do that'd probably be a cheaper way to do it. You won't get OTA synching though.
OK, good, MobileMe it is then. I just thought somewhere it said MobileMe wouldn't work. So we can both just publish our calendar and have the other person subscribe and we'll see it on the iPhone?