I have received requests for a sort of Japan rough guide, Tokyo in particular. Here is a first draft of this post. Let me know what you think!
For getting about.
I never got one, but you would have a much better time getting around if you get a tourist map of Tokyo, available at the Tokyo train station. If you take the Shinkansen(bullet train) you will arrive there. There will be a sign for an information counter where the maps are!

For staying:
I stayed at the Cerulean Tower which is a pretty grand western style business-y hotel with large, clean rooms located centrally in Shibuya. Everything about the place was great but it didn’t have a lot of character. However everyone there was very helpful which is what I needed to get oriented when I arrived. The hotel is right near the station, and this is one of the 2-3 main train stations in Tokyo on the JR “loop” line that gets you almost everywhere.
Other recommendations are the Asia Center of Japan, which has very inexpensive rooms, but I hear a lot of good things about it. There is also a boutique hotel, Claska, that I wanted to try but it is a bit out of the way, in Meguro. I will probably stay there next time. If money is no object, the Park Hyatt or Grand Hyatt is the obvious choice.
For eating and drinking.
Tenmatsu was the best tempura I have ever had. This is right near Shibuya station, but definitely get directions and make a reservation if you can (requires a Japanese speaking person), as they only have seating for about 10 at a time. 1-6-1 Dogen-zaka, Shibuya-ku, 03-3462-2815
Sukeroku is some of the best sushi in the world. I am sure I am not biased as the sushi master and his family has shown me unbelievable hospitality. Please try to visit and let them know that Melissa-san sent you! Definitely get directions for the train (Kameido station on the sobu line, east exit I think) and also an area map for the street as there is no sign on the restaurant, just the address. People in the neighborhood can help you find it too as it is well known. 6-22-8 Kameido, Kotoh-ku, 03-3638-1169. Also his assistant is Kobori Takashi and he speaks a little english.

Daiwa Sushi is just outside of the Tsukiji Fish Market, and is best before 8am otherwise it gets crowded. (I know, lines for sushi breakfast, its weird) So after you see the market walk outside of it and you should see numbered buildings - it is in building 6. This is the outer market where they sell vegetables, trinkets and tea and such, the inner market is just sushi. Try to get to the central fish market around 5am for the tuna auction. Check with the hotel where you are staying and make sure it is open when you are planning to go, it is closed on random days.
The Pink Cow in Shibuya is like home, or at least a California hippie version of home. Everyone here is sooo friendly and Traci (the owner) is a doll and will welcome you and is a wealth of information about the city. It is off the main drag so look at their website for directions from where you are.
For nightlife check out Superdeluxe (loft-like bar), Alife or The Baron (bar in the back of this club) or Yellow, all in the Roppongi area. Just be forwarned, if you are out past midnight you will probably be out until 4:30 when the trains start running again. After the witching hour bars and clubs take on the atmosphere of a school lock-in, with alcohol and a bunch of people that you mostly can’t understand that is.

Sights.
Tokyo National Museum in Ueno, the worlds largest collection of japanese art. Dont miss the gallery of Horyuji treasures (yes the same Horyuji as in Nara, minus the deer and plus the treasures). Harajiku and Aoyama area for the fashion and the fashionable, especially on weekends. And a visit to the Meiji shrine in this area. There is a great tshirt shop here, Graniph, and the english sayings on the shirts mostly make sense, which can be a rarity. If you are into home design Muji in Ginza is not to be missed. If you are in to luxury goods, Mikimoto (the new building), Hermes and Prada all have a fantastic selection of bank-breaking items, and the great architecture of these buildings is an added bonus.
The Hama Rikyu gardens, this is near the fish market and is good for a walk after sushi breakfast. They have lots of poison flowers, an ancient cypress that is barely standing, giant aloe plants and a shogun inn where you can have tea.
Outside Tokyo.
I wish that I had the time to visit Hakone, Nikko or Mashiko around Mt. Fuji, all have great onsen (baths) and views. Let me know if you make it there I will be envious.
Of course if you have 2 days or more to travel outside of Tokyo, Kyoto is a must.