Fuji is often visible from Tokyo in March. You may enjoy Hakone, which is reachable either by private train from Tokyo-Shinjuku or from the Shinkansen stop at Odawara (only the slower Kodama Shinkansen trains stop at Odawara). The Hakone Free Pass, purchased either at Shinjuku or at Odawara gives you rides through the area on a series of sometimes touristy conveyances, and there are plenty of places to stay.
Going to Koya-san will take you through plenty of countryside. It's the top of a mountain, and you go through a lot of small towns and wooded areas to get there. By the way, the easiest way to reach Koya-san, especially if you don't have a JR Pass, is the train from Osaka's Nankai Namba Station, so I would suggest modifying the order of your trip.