For Japanese curry, I voted for Coco's not only for the spicy meter, but for the ability to get cheese.
Indian curry was a bit tougher because so much of it was related to how good the naan was. I found a nice little place in Nagoya that had about 8 different kinds of naan that really affected the way the curry tasted, but was easily my favorite. Don't think I ever got the name.