I've been living in Madison for about 5 years now. My wife and I both went to grad school here, and we stuck around after for work.
The city is just great. You usually hear people say how it has big city culture and opportunities combined with smaller city benefits, sort of the best of both worlds I guess. It's also nestled on an isthmus between two nice, large lakes so it has some natural beauty as well. The UW and state governments sort of dominate the downtown area, but with about 500,000 people in Dane County you'd be surprised how many other kinds of jobs and opportunities are around. You're also only 90 miles from Milwaukee, and about 150 miles from Chicago, so bigger city weekends are possible. Cheaper airfare, too.
Madison is known in the area for being fiercely liberal/progressive and having some pretty darn impressive farmers markets. Seriously, I was new to the midwest, but people just love strolling past produce on Saturday mornings at the Capitol square. The city also boasts State St., a one-mile pedestrian street that links the Capitol and the university. It has lots of bookstores, coffee shops, bars, restaurants, and boutique kinds of stores. I've heard that Madison has the most restaurants per capita and I don't know if it's true but I wouldn't be surprised, there are a lot of options. I've also heard Madison has an unusually large number of non-profit/volunteer types of jobs, the sort you would find on http://www.idealist.org. My wife and I have been here 5 years (she's a poet, I'm a statistician) and we've always found things for both of us to do. Nice balance.
Rent seems reasonable. I live on the near-east side (Willy St. area) which is a preferred spot for graduate students. Most of the apartments are in converted 1920s houses and go for about $600 studio, $750 1 bedroom, $900+ for 2 bedrooms. Lots of new condos going up too. I think our neighborhood is considered a bit pricey for rent, so there are probably cheaper options elsewhere. Anything within a mile of campus will be heavily dominated by undergraduate students with very limited parking. I also spent a year in University Graduate Student Housing (Eagle Heights) which was more affordable and right on one lake, but also somewhat cut off from the downtown area of the city. The city bus system is wonderful (and free to students!) so don't be worried about living too far away from campus. Cars are helpful for grocery stores and errands, but not strictly required.
Any drawbacks? Let's see... if you are coming from a bigger city Madison will probably feel somewhat small and more limited. We really don't have a "buzz" like Chicago or NY. Madison is also less diverse than bigger cities. Oh, how could I forget the weather... unless you are coming from Anchorage, Alaska or Duluth, Minnesota, you will find it cold in the winter. It can stay below 20 degrees for weeks with a steady wind whipping across the lakes. Bring a parka, and lose your prejudice against wearing long underwear daily. Other seasons are just beautiful.
Best of luck with wherever you move.