In terminal 1 of Narita airport there are two sushi shops: Sushi Iwa and Kyotaru. Kyotaru is a big chain and fairly low quality. Sushi Iwa on the other hand is a high quality sushi joint that I ALWAYS go to before leaving Japan on a trip. After the rennovation of terminal 1, Sushi Iwa significantly upgraded the quality of the material they serve and is definitely a treat. The staff are friendly and happy to fulfill any silly requests. They will also pack boxes to go if you want to eat it on the plane. When you go, sit at the counter. Also, remember that the material will get better as the staff get to know you. This is true in any sushi shop since on every piece of fish, there are tasty bits, and not as tasty bits. I find this is true in Chinese restaurants as well... Saegusa-san thinks that chefs can only make a few truely good meals every evening and they choose who gets them. Anyway, smile at the sushi chefs a lot and ask for a recommendation and you'll probably get something good.
As usual, I had a wonderful meal before I left. The shellfish were especially good today.
I just arrived in Aspen after stopping in Seattle and Denver and I haven't eaten anything since my sushi. ;-)