It's killin' me I don't have my Japan travel books here, since I made notes of where we stayed, but we mostly stayed in ryokans in Tokyo and Kyoto. Only spent one night in Osaka, at a Holiday Inn Express which was neither central nor inexpensive. If you're travelling by train, sometimes the JR has special deals at JR Hotels, which can be a cheap option - stop by one of the major train stations info booths to see what they can recommend. Also, any travel agent should have info about ryokans, there's a big catalogue of them available. If language is an issue, head out towards Yokota Air Base, there will be a bunch of local travel agents which cater to the American trade and they'll be able to help you in English.