This is the "must-see" Japanese itinerary based on my time there. I'm sure there are things I missed, and there are certainly some things I did that I am excluding, but this should be a good starting point! Most of these days are planned around being close to each other, so the order isn't important, but the days are easier if grouped like this.
Tokyo
Day 1
I recommend taking the first day in any country pretty easy, and we stayed in Asakusa. This area is perfect as it is quite cheap and quiet at night, with tons of public transport options to get anywhere in the city.
Senso-ji Temple
This is a MUST SEE in Japan. It is the oldest temple in all of Japan, and has an excellent market in the road leading up to the temple. Plenty of food options, and an incredible sight, with towering red pillars and buildings.
You will need at least an hour to see this, but could easily spend a few hours wandering around the huge complex, and just people watching.
Asakusa
There are heaps of dinner options and a few onsens (traditional bath houses) in the area for a quiet first night.
Day 2
Central Tokyo
The main Tokyo station is quite interesting, and the area around it full of high end retail shops. There is not much to see and do in this area though as it is mostly a business district.
Emperor's Palace and Imperial Gardens
If you time it right, there is a free walking tour that leads you through the Emperor's Garden each Saturday and some other days which was incredibly informative, and gave the place much more life than just a garden. http://www.tfwt.jp/Pages/default.aspx#_=_
The Palace itself is only open on very special occasions, and is not that interesting to just look at.
Akihabara
This is every nerd's wildest dream. Rows of electronic stores, game themed bars and adult stores with all of the weird, crazy stuff that makes you say "oh, Japan".
It really is best seen by night as the neon lights are amazing, and the stores are open well into the night. I recommend a stop in at Yodabashi, the biggest range of electronics in one giant store I have ever encountered.
Day 3
Tsukiji Fish Markets
A smelly must see, but an early start. If you are visiting, make sure you check whether the tuna markets are open to the public, as they are closed part of the year.
The rest of the market is a great place to see tradition and current technology working together, with old-school techniques being shown off right next to new. Super fresh seafood to be had at many small shops.
Tokyo Municipal Government Building
This is completely FREE and gives one of the best views of the city. There are two towers, and they give very similar, almost 360 degree views of Tokyo. The lines can be quite long at times, but it is worth finding the time to visit.
Meiji Jingu Shrine
One of the most peaceful places in the city, surrounded by chaos on all sides. Keep an eye out for business people "Salary Men" on a lunch break wandering through the gardens, taking some time from of their crazy schedules.
Shibuya
The "cool district". If you arrive in the afternoon and do some sightseeing, you can stick around and spend the whole night in this hip part of town. Plenty of bars and clubs, and late night shopping.
The Shibuya Crossing is one must see, on par with Time Square in New York.
Stop by the statue of Hachiko, the loyal Akita dog who went to the station every day to wait for his owner, continuing even long after his owner had passed away.
Optional Extras
Disney
All Disney lovers, and even people who just like the rides will love this park. Get there early, stay until close, and go on every ride.
Some of the rides are strangely dark, and it is a great place to see the Japanese custom of lining up for EVERYTHING. They are very organised people, and will line for food, rides, toilets, photo opportunities and even lines for lines.
Harajuku
The girliest street in the world, full of pink, Paris and Hello Kitty paraphernalia, if you are into cutesy "kawaii" things, it is certainly an experience unlike any other. The first Sunday of every month they also have an informal gathering of girls dressed in full "doll" get up which would have been amazing to see.
Robot Restaurant
This is an experience. Down in a dark basement, there are robots and pretty girls. If you are intrigued by the sound of this go, if not, it will definitely be way too weird for you, and you should just leave it alone. Easily the weirdest stage show I've ever seen.
Oeno Park
Nice for a bit of a walk though if you find yourself with some spare time. There is a temple, and a zoo inside, which is worth having a look though if you are in the area, but is not a Tokyo essential.
Kyoto
Day 1
Gion
This is the area of town we stayed in, which was relatively cheap, and surrounded by heaps of traditional buildings, on the first day, we even saw some Geishas walking the street, who were more than happy to stop and take a quick photo with us (despite their expressions).
There are hundreds of temples in this district though, so make sure you have a good map, because it can be very disorientating!
Arashiyama Bamboo Forest
This area is really a whole day trip in itself. Start off with a walk through the bamboo forest, and look at some of the amazing temples and gardens along the path. You can get into the gardens of most of them for free, and only if you really want to do you have to pay to get inside. You'll see a lot of free temples though, so I'm not convinced these are worth it.
Seeing it during the day, then going back after dark is the best way to see it as it is lit up with multicoloured lights at night, with lanterns dotting the path.
Monkey Mountain
The part of town is beautiful, and a short walk, and a hike up the side of a mountain will take you there. There are hundreds of fluffy Macaws who, depending on the time of year, hang out for food, bath in the ponds, climb all over the trees and are just completely cute.
They aren't as aggressive as the monkeys I've encountered in other parts of Asia, but never mess with a monkey.
Day 2
Imperial Palace
You have to get up early to try to get tickets to go on a tour of this building, which we didn't realise, but the gardens are quite nice to walk through.
Nijo-jo Mae
Nijo Castle was built in 1604 and the castle and surrounding gardens are amazing. The museum has some of the original trims on display as the castle itself has mostly reproductions on show, but the real standout is the gardens.
Day 3
Ryoan-ji Zen Garden
When you picture a Japanese Zen Garden, this is probably the one you're seeing. Get there as early as possible, when it opens, as the peace is completely lost when it's crammed with other tourists.
If you get lucky like us, the only other people there may be monks from another part of the country on holiday, taking selfies with the stones.
Kinkaku-ji Temple
Real gold and lacquer, there is no way to take a bad photo of this place. Again, it's a tourist hotspot, so get in early to avoid being trampled!
Fushimi-Inari
Tens of thousands of bright orange torii gates line the path up the mountain. Honestly, the best part is the first half where it comes to a stop where you can look out over all of Kyoto, but if you are particularly keen, you can walk up the whole mountain. Don't expect a medal or any real payoff though, as there isn't much at the top, other than super athletic seniors who practically jog past you as you pant up the hill.
Optional Extras:
Tea Ceremonies
Tradition is Kyoto's main drawcard, and there are plenty of places you can go and take part in a traditional tea ceremony.
Onsens
These traditional public bath houses are an integral part of Japan's past and are still dotted throughout the country today. Some places are strict about tattoos though, as they are almost all separated by gender.
Hiroshima
Day 1
Peace Memorial
This won't take a whole day, but you won't want to do anything else after visiting the Museum and the Park. It's terribly tragic, but the message of peace and love the place leaves you with is great.
Optional Extras
Hiroshima Castle
Rebuilt in the 1950s after being destroyed, the inside is more of a museum than a castle, but the outside is nice, and the view from the top looks out over all of the city.
Shikkei-en Garden
Signifying the whole of the district in miniature form, it has been tended and maintained for hundreds of years. There is an incredible number of Koi fish under the bridge which swam when you feed them.
Day Trips
Miyajima
Deer island as it is affectionately known has a large population of deer. The main attraction is the giant Torii gate which appears to "float" for much of the day, out in the middle of the ocean, but at low tide, you are able to walk right out to it.
There is a huge cable car up towards the top of the mountain, and then an uphill walk, but up there is the eternal flame - burning since the island was first inhabited in the 800s by a monk seeking enlightenment. The view from the top is incredible, and the buildings up there are just so ancient.
There is also a lot of amazing food to be had on the island, all unique to Japan.
Iwakuni
A small fishing town with a lot of history and character. The bridge is pretty cool to walk over, and there are heaps of beautiful places to walk around.
Osaka
Day 1
Osaka Castle
This is another castle turned into museum, and by this stage, we had seen a lot of better castles. While it was interesting, as it was so late in the trip, I'm not sure it was worth going inside, as the outside and gardens were much nicer.
Dotonbori
A huge shopping district. HUGE. There are plenty of high end stores as well as bargains to be found here. Don't be intimidated by the people shouting things from out the front of every store!
Day 2
Nara
Technically a day trip out of town, this is a MUST. The whole town is overrun with deer! If you hold up your food, they will even bow to you. Getting away from the main tourist areas is pretty easy, and the temples around the area are beautifully set among the deer. The further out you get, the more shy the deer are though.
There is also an abandoned theme park here that you can break into, but we did not as it was a busy holiday time and there were just too many people around.
Optional Extras
Osaka Aquarium
Usually I'm not one for things like this as a tourist in a city, but this aquarium is huge! They have a whale shark. It's a solid half-day to see the whole thing!
There is a huge ferris wheel near the aquarium too, with views out over the whole city. Waiting in line for the clear carriage was worth it, as you could see out of every surface, including straight down through the floor