I don't have koi, but people who do say they really love depth. I'd give them at least a large, four foot deep hole they can swim down into. My pond is a little over 1000 gallons, but I decided to stick with goldfish because it's just too shallow for koi to be comfortable.
I just read a post on another forum by someone who reconfigured his pond to be easier to clean and made it too shallow. Now his koi stay as deep as they can and never come to the surface. Before, they weren't so shy, presumably because they knew they had a deep hole to dive into.
Keep in mind that surface area is important too. More surface area means more oxygen for your fish. Aeration, waterfalls, and trickle filters will all oxygenate the water, but it's better if your fish don't depend too heavily on pumps for their oxygen. Half an inch of koi for every square foot of surface area is one rule of thumb. Here are a couple articles on surface area requirements.
How many fish can I put in my pond - answers, supplies and more here at AbsolutePonds.com http://www.buildagardenpond.com/arti...ypondfish.html
WAC is right. Many first time ponders wish they'd made the pond larger and deeper. Consider not only what you need for your koi, but the oxygen demands of their offspring or the minnows you might stock for your koi's snacks and entertainment. If you build a pond, will you really be satisfied with having only two fish in it? Leave yourself room for more, and you'll have no regrets later.