You pick a good time to travel, and whether it is south to north or vice versa is up to you. For warmer weather, I'd probably do the former, and you can also see some of the spring flowers. You might not see much if any of the cherry blossoms, but few people explore the other wonders that come out - the wisteria, the azaleas, roses, etc. I would definitely not divide your time equally between Japan's various regions - they are not at all the same and spending the same time in Shikoku as you would in Tohoku or the Chugoku region makes little sense.
Regarding Golden Week, what you need to know is that it doesn't have to be as bad as some make it out to be - the mass exodus of people from big cities at the beginning and return at the end is something you should try to avoid if possible. But if you are not going in the same direction and not fighting the Japanese over the same seats, then you can still have a fairly easy time.
Given the long length of your trip, basing yourself the whole time in just one area is severely handicapping yourself. The extreme opposite of barnstorming the country and staying at a different place every night is not much better though, and will likely cause you to eventually burn out. Most likely something in between would work better for you - pick one or a few bases in a given area and do some day trips that way.
As far as the sample itinerary page you linked to, you can use it for some ideas and suggestions, but in the end, if you want the best trip you can make, you need to tailor it to your own specific interests and travel pace. Not to mention if there is someplace at a specific time you want to be, such as to attend a festival. The other
big question you have to ask is if you think you will return to Japan again someday. You won't see the whole country in 2 months (nobody can) - so if the answer is yes, it would likely serve you better to pick a given part of the country and leave the rest for a future trip - Japan will still be there.
Are there many places left out of it?
There's a whole mountainload of places left out. There are many good places listed, but I could list a bigger number of places it didn't. As for what you should see and do, it is up to you to do your homework and make a plan - this whole site is a good start. But also look at www.jnto.go.jp for more ideas, as well as the official websites of cities and prefectures - they pretty much all have a good tourism guide with places listed nowhere else. Tripadvisor also has a large database. Youtube has some great channels to view.
https://www.youtube.com/user/ChannelAGG/videoshttps://www.youtube.com/user/thejapanfaq/videoshttps://www.youtube.com/user/hanazakurasakura/videosFor some festivals, you might look at
http://www.japanvisitor.com/japanese-festivals/festival-aprilhttp://www.jnto.go.jp/special_events/eng/index.phpFor other activities, I highly recommend getting involved in some. You mentioned hiking, and in a country with close to 70% being mountainous, there is no shortage. You could browse here for example.
https://japanhike.wordpress.comOr you can combine some sights with some hiking, like seeing the wondrous Akiyoshido Cave along with the hiking at Akiyoshidai on the surface.
https://youtu.be/DqIKC9S8TFQTrying your hand at some folk crafts or cultural activities is another idea, like
http://www.ti-yanesen.jp/en/Or even in the cities, Tokyo has a big number of beautiful historical gardens to visit.
https://goo.gl/tAECfMVisiting some hot springs is an excellent way to immerse yourself in Japan (sorry for the pun). Even just visiting a supermarket is insightful - look at what Japanese buy and eat, plus how much they pay. Walk through a typical residential neighborhood and see how they live.
You still have lots of time for research and planning, so make your dream trip come true.
