Everyone will tell you to visit the Hama Detached Palace Garden (Hama Rikyu). This is a vast garden on Tokyo Bay with a salt water pond, an attractive tea house, some flower beds, and a ferry terminal that will get you up the Sumida River to Asakusa. The whole place was burned by an American bombing raid on November 29, 1944. Personally I don't like the scale of Hama Rikyu and there aren't any Koi ponds.
Kyu Shiba Rikyu appears to be "right around the corner" from Hama Rikyu. In fact it is a 20-minute walk, enervating in the hot humid summer. This is an old garden with frisky Koi and a pleasant human scale, surrounded by towers and a train station that provide evidence of the contrast between Edo and modern Tokyo.
This is the 16-acre remnant of what was built from 1629 as a 64-acre garden. The garden took 30 years to build and required consultations from Zu Shu Shui, an exiled Chinese scholar. The center of the garden is a huge pond stocked with undistinguished Koi.
Getting there: Take the Maunouchi or Namboku lines to the Korakuen station. From there it is a 10-minute walk along an expressway to the gardens.
The New Otani Hotel was built around an existing Edo-era stroll garden. The 400-year-old garden has been preserved and contains a wealth of beautiful koi.
Gardens are usually open from 9-5 every day. They'll sell refreshments and have a clean restroom. A typical entrance fee is $3 or $5. Restrictions on photography or tripod use are rare.