[Update:] See this more up-to-date and comprehensive listing of Japanese groceries and other related stores in the New York area , with addresses, hours and phone numbers.
Whenever I go to New York I stock up on as much Japanese groceries as I can manage. Prices there are cheaper and the selection much bigger than at the tiny Japanese grocery in Zürich, Nishi's Japan Shop. Here's a biased overview of the Japanese grocery stores and other places to get Japanese foodstuffs in the New York City area that I have been to. (See this page  for addresses.)
If you can spare the time, it is well worth making the trek across the Hudson to Mitsuwa, formerly Yaohan, the big Japanese supermarket in Edgewater, New Jersey. (It was built here because Fort Lee used to be a favorite location for Japanese business men on temporary assignment to live with their families.) It has the biggest selection by far, especially of staple items like rice, soy sauce, and sesame oil. The mini-restaurant row in the back of the store, complete with plastic versions of the dishes on offer, is quite entertaining if you've never been to Japan. It's much more convenient with a car, but there is a shuttle bus from the Port Authority Bus Terminal . Most of the major signage for specials and such is in Japanese only, but individual items are usually labeled in English. The book/stationery store in the adjacent mini-mall is nice too.
The selection at all of the Manhattan Japanese grocery stores is pretty much the same. Of these, I like JAS Mart a bit more than Katagiri for overall quality and friendliness. However, Katagiri may have the edge on raw sashimi-quality fish and the like. It's also the priciest.
The very popular Sunrise Mart is my least favorite Japanese grocery mini-chain. They over refrigerate all of their readymade obento and other meals to the point of making them hard and inedible; if you make the mistake of buying their onigiri, be sure you have access to a microwave oven, though that won't really make the badly cooked rice that much better. Still it is fine for your Japanese grocery basics, and since it is quite popular the stock is usually fresh.
Incidentally, Katagiri seems to have the most helpful-to-hapless-non-Japanese Japanese-expat customers from what I've observed, possibly because of its midtown location and the fact that the store has been around for decades.
Korean grocery stores such as Han Ah Rheum and m2m also carry a big selection of Japanese groceries.
The grocery stores in the suburbs, including Mitsuwa, tend to maintain a higher level of quality than the ones in the city, especially for fresh produce and readymade meals. I think this is because the ones in the city cater to a student and young-people customer base, and the suburban ones have more wives of businessmen as customers. Housewives are usually pickier than students.
I go to two of them fairly often since I have family on Long Island: Nara Foods in Port Washington, and Shin Nippondo in Roslyn. Both are good small stores. Shin Nippondo may be slightly better stocked than Nara, but you can get all your basics at either place.
Beard Papa is a Japanese chain that sells cream puffs. See my previous comments .
Panya Bakery sells Japanese baked goods. Japanese sliced white bread is the best sliced white bread in the world, simply delicious for delicate English-style tea sandwiches and as buttered toast. Just about everything they carry is authentic middlebrow Japanese-style; melon pan, anpan, cream horn, etc. (The store name bugs me: since Panya means bakery in Japanese, the full name is Bakery Bakery. Anyway...)
Minamoto Kitchoan carries traditional Japanese snacks, most of which are bean-paste based. It's inferior in quality to Toraya, which sadly closed a few years ago. Toraya used to make all of their fresh snacks in-house, but Minamoto Kitchoan only sells pre-packaged goods.
The tiny Oms/B store near Grand Central Station makes quite edible onigiri/omusubi (rice balls). Their nori-wrapped ones are made to order with warm rice.
You can go to a reputable non-Japanese fishmonger like Citarella nowadays for sashimi-quality fish. You can also special order very thinly sliced beef for sukiyaki and shabu-shabu from a good butcher like Lobels or Schaller and Weber. (Note: to buy meat at Lobels, you will need to take out a second mortgage on your house.)
(Note: I was about to take out the following reference to Aji Ichiban, since upon reflection this is not really a Japanese food store at all; it's a Hong Kong snack store with a few Japanese-style snacks, but mainly carried dried fruits and other snacks more familiar in China/Hong Kong. It is somewhat puzzing why they call themselves by a Japanese name, but I have seen this trend elsewhere...sort of like Japanese stores or brands giving themselves American-sounding names. In any case the listing is still here, with the caveat that this is not a Japanese food store despite the name.)
Aji Ichiban (which means 'taste number one' in Japanese), a Hong Kong based snack store chain, sells a lot of prepackaged house brand snacks, plus a big variety of interesting dried fruits and things. (Note: The first time I went here they were very friendly, but the second time they were decidedly not. They were outright rude actually. So, I guess it's good to watch out. And they do not, emphasize not, like you taking pictures. I guess they don't realize it's free publicity for them, but oh well. Incidentally, a reader points out correctly that this is not the place to go if you want Japanese brand snacks. Aji Ichiban sticks strictly to house brands.)