Hi!
I just wanted to add a little weight to the Madison side. I think I have a pretty good perspective on both places- I have been living in Madison for a year and a half and I grew up in Michigan (near Lansing) and though I went to school at MSU (which admittedly colors my perception of Ann Arbor, but to be fair, I didn't really want to like Madison all that well either), I spent a lot of time in Ann Arbor and have/had a lot of friends who still live there. That said, I think Madison is the hands down choice in terms of quality of living. Don't get me wrong, I like Ann Arbor, there are great and fun things to do (ABC, Ashley's and Zingerman's will always be favorites of mine) but Madison just beats it on all fronts.
First, Madison is just a gorgeous city. It's hard to appreciate it during the winter, but once spring and summer come it's amazing. The city is sandwiched between 2 lakes and there are so many beautiful places to go for a run, long bike ride, or just sit outside and have a beer (especially the Memorial Union Terrace) that it's really mind boggling. You really don't ever need a car- the city is unbelievably bike friendly and in the winter, you can always walk/take the bus if you prefer. Also, There is a surprisingly good restaurant scene for the size of the city, and there is always something to do. The people are friendly and down to earth (I doubt you'll ever hear anyone in Madison calling the UW the 'Harvard of the Midwest'). Additionally, the city's economy has weathered the recession pretty well. It seems like that's a strange thing to think about, but it is nice to not have the spectre of the dying auto industry hanging so close overhead. Moreover, Madison may not be as close to Detroit as Ann Arbor is, but Milwaukee is only an 1-1.5 hours away by car and Chicago is not much more (2 or 2.5 hrs) if you ever need to get some big city back in your blood. The live music scene in Madison is pretty OK (the high noon and the Barrymore get some pretty great acts going through) but anyone you'd ever want to see ever will likely go through Milwaukee or definitely Chicago, so you won't miss out on anything by living here.
The cost of living is probably a shade less than in Ann Arbor. You can overpay for some of the condos downtown, but it's easy to find a really great place really close to the downtown/campus area for around 900-1100 for a 2 bedroom place. If you're looking around, I would recommend looking near East Johnson St, or Williamson St. (on the east side, near some really cool independent bars/restaurants or in the Vilas neighborhood (super close to campus, tons of grad students). In my own grad search, I've been trying to estimate cost of living by the price of a good pint of microbrew. Around here it's about 4 bucks a pint for something good quality and local (definitely goes lower, can go a touch higher). Which leads me to another point- the Madison area has a ton of micro breweries, and some of them are really, really good.
There are downsides of course- Madison is a little colder than Mid-Michigan in the winter (especially in December) and though Madison has plenty to do, it's not a major city. Also, Madison's not a very racially diverse city. From my time here I get the sense that the minority communities in Madison are not nearly as large nor as visibly present as I have seen in other cities. I think that has been the one thing that struck me as a bit strange. So, if that is something that would be important to you, it's worth bearing in mind.
All in all though, I think between the two, I would choose Madison every time. The weather and the geography just get me every time, Madison is just unbelievable in the summer. (Did I mention it's much much sunnier here than in Michigan?) Anyway, good luck deciding. Since you are picking between 2 really great places, you can't go wrong either way!