There are a couple of things that sprung to mind here.
One is that the most demanding part of most open water diving is hauling the gear around. If you are working hard underwater, you are most likely doing something wrong. What happens to new divers is that, because they are not balanced underwater, they are forced to swim constantly. When you combine that with finning technique which is not very efficient (bicycle kicking), you end up with a tremendous amount of work being done for very little actual return.
Time spent getting your gear balanced, learning to stay horizontal, and learning to kick properly will reduce the physical demands. In addition, using strategy helps -- Swimming into strong current is exhausting and blows through one's gas; if heavy current is encountered, it's best to change the dive plan and swim across it or drift with it (or abort the dive, if neither is possible).
That said, some amount of swimming, both on the surface and underwater, is required to dive, and hauling gear IS difficult for someone who hasn't picked up anything heavier than a suitcase in 50 years (which is where I was when I started diving). A regular pattern at a gym, mixing strength training with some cardio (I use swimming) DOES make these things easier.
Somebody already gave you the link to Cameron Martz's website above -- He has a VERY nice book out on fitness for divers, as well.
