Welcome to MDTP Leuco!
I agree that looking for a place in Madison can be a difficult one especially when you don't have the luxury of easily looking at the apartments first. Have you looked at applying for University housing? Eagle Heights doesn't seem that fancy, but it is (very) quiet and the rents are reasonable by Madison standards, however they have a no cats and dogs policy which is unfortunate. Alternatively, a lot of grad students seem to end up living by the Capitol, where parking is difficult (i.e. you're going to be paying monthly for a spot) but life if otherwise pretty good and you're centrally located to most things. I just checked Craigslist and I see a couple of flats in that area around $700/month.
There are a large number of apartment buildings currently being built right next to campus which I suspect are very, very undergrad-y, and also very expensive. The flipside is that other areas just a mile or two from campus seem to be increasingly depleted of students. A lot of people are very negative about the area around Allied Drive on the south side of the city as this is a socioeconomically challenged area. However, these things are relative and depending on where you are coming from the "bad area" of Madison isn't really that bad. Likewise, there's a sketchy area on the east side by Rt 30 and East Washington (Worthington Park) that I wouldn't recommend. Also, it seems like everyone hates the apartment management companies and Madison Property Management in particular for screwing people out of their security deposits.