I will be going to Tokyo in late May for business for a few days. I plan to take the next week off and explore. I have been to Tokyo before once and know that there is a lifetime of exploration possibilities. I would like to check out some other places though.

I can pretty much go anywhere and am open minded. Usually appreciate food and culture (new and old), with some history mixed in. Like to walk a lot. Some ideas that have been burrowing in my head have included Osaka and Kyoto (the latter is better in the fall, I hear?), Mount Koya (which I read about once a few years back but sounded stunning).

In my mid to late 20s, don't speak Japanese (though I speak Mandarin, and am also more than happy to play charades to get my point across) and no dietary restrictions if that helps..

Any thoughts and suggestions are more than welcome!

Kyoto does sound ideal for your requirements.
I'd suggest getting hold of the Diane Durston book - Kyoto, seven paths to the heart of the city and you could easily base an intensely satisfying holiday on this - with the option of visiting Koya San (and anywhere else in the vicinity, even Kanazawa, famed for its seafood, is an easy destination from Kyoto.)
If you want a bit more variety I'd suggest:
Morning in Matsumoto, head off to Takayama. Stay. Get bus to Shirakawa go, visit, continue by bus to Kanazawa. Stay. Train to Kyoto. Stay (optional visit to Koya San) return to Tokyo if no open jaw ticket available.

If budget is a concern you could take advantage of the JR East pass special and travel around Eastern/Northern Japan for a third of the price of the JR rail pass.

What LapLap said, including the part about the Diane Durston book.

Kyoto is just fine in May and a lot less crowded than it would be in the fall or in the cherry blossom season.

Mt. Koya should be an overnight trip, since the essence of the experience is spending a night in a monastery. Any of the major guidebooks will tell you how to reserve a place.

Thanks to all. This was my first thought (Osaka/Kyoto etc). I also have a friend who's doing JET way down in the southern part of the country and he said the same. I have gone back to him to ask if there are any places that he specifically wants to see/do and I could just tag along (he's a Japanese speaker).

Any other ideas/suggestions are always more than welcome.