[blimp]

just to add to nyororin's excellent info.
one thing that might be good to keep in mind is to try to get a flat not too far from the station. this not only cuts down on the commuting time but it also lessens the time you have to walk outside in the summer, which is hot, hot, hot. of course the closer to the station, the more expensive.

for you to get a non-"non-japanese" catered flat you might want to involve your company as much as possible, as it might be difficult for you to get a flat on your own just off the boat. if the company you works for is very famous this might not be much of a problem. with your budget you might be

in tokyo it is rather straight forward, not like osaka. you usually pay
deposit (敷金）(0-3 months, the most common is two I would say),
key money （礼金）(0-2 months, as nyrororin correctly pointed out, it is nowadays common to see flats without key money)
broker's fee(紹介料)(usually 1 month, some agencies have half a month)
and then one month's rent up front.
to this you add compulsory insurance (already decided for you) (between 20,000-30,000 yen) and perhaps some special fees; a rent guarantor, changing of the looks, extermination of bugs, and what not.

keep in mind that if you stay for a longer period, longer than two years, you might have to extend your contract which is usually a fee of 1 month's rent.