Depends on the purpose of your visit, how long you plan on staying, what kind of references/credit you have, etc. Renting is not as easy as one may think without someone fluent in Japanese to help negotiate your lease (assuming you and your partner don't speak the language). Not to mention you'll most likely need someone (a Japanese guarantor) to vouch for you. Key money is unavoidable unless you go through one of those intermediary agencies that can secure housing for you (not too familiar with them so I can't address any specifics).
From my experience and those that I have heard from others, foreigners are often denied contracts simply because they are foreign and the owners anticipate problems/miscommunication down the road. There's really quite a few things you need to fork over for if you're planning on finding a place like "Ya-chin" (rent), "Shiki-kin" (deposit for maintenance, upkeep, etc.), "Rei-kin" (money given to owner aka "renter's gratitude"), "Chukai-Tetsuryo" (another nominal fee), "Kyoeki-hi" (set monthly maintenance/cleaning fee) and who no knows what else. 8-p Anyways, good luck in your search for a place and hope you find what you're looking for.
