I was pleasantly surprised when I visited Milwaukee a few years back. Nice little city. Ditto Nashville. I'll also give a plug for my hometown: Vancouver

(I know a lot of my friends would take umbrage and consider Vancouver a big city, but they'd be wrong. They just haven't been to many big cities.)

Its a super liberal city. Its also a big college party town if you google haloween in madison, things where kind of crazy although tamed down in recent years. When I live there it wasn't downtown where all the fun happens

Since I live between Milwaukee and Madison let me recommend Milwaukee - by far - over Madison. I find Madison extremely boring as it is just a college town to me and I am so beyond that. Milwaukee during festival season (all summer) is much more likable I think for mature people. Plus it's on a great lake!

Savannah

Buffalo/Niagara

Everglades City

Portland, OR
Nashville, TN
Austin, TX

deleted

Somebody a bit earlier asked things I'm into to help narrow it down a bit. I'm really into classical music and travel all over to see concerts. I also enjoy photography, especially some of the unusual things you see.

My St. Louis trip I found fun after an evening at the St. Louis Symphony, a photography evening at the City Museum (what a crazy place that is!), and some of the best barbecue I've ever had at Pappy's.

Conversely, I didn't find myself able to get into Austin that much - lots of live music and drinking, but not much else. I think those days are ten years behind me.

So I guess you could classify me as more of an arts-and-food junkie rather than a party junkie.

I'm a little surprised at the answers so far - not that the suggestions aren't good, but that many of the cities mentioned don't fit my definition of "small or medium" (I do understand that each of us will have his/her own feeling on this).

I think of "medium" as maybe 50,000 to 300,000 population, and "small" as under 50k population.

For "interesting", the first place that came to my mind is Columbus, Indiana, population about 40,000. What distinguishes this town from any rural Midwestern county seat is its architecture - the CEO of Cummins Engine Co. (Cummins Diesel) instituted a program under which the company paid architect's fees for public and private buildings, resulting in schools, churches, government and commercial buildings from the likes of Eero Saarinen, I.M. Pei, Robert Venturi, Cesar Pelli, Richard Meier and others.

Visiting the town, it's interesting how the architectural works are integrated into the framework of the town as a whole - these are not sterile, stand-offish structures.

Savannah, GA
Charleston, SC
Memphis, TN - (for the Blues)
Nashville, TN
Asheville, NC (Smokey Mt area)
Door County, WI (the "Cape Cod" of the Midwest)

Make note - For any of these small cities you are hearing about, you can't just drop in unprepared and expect to have a good time. You'll need to research where to go, where to eat, etc.

wonder why noone said midwest cities.

Cincinnati, OH during the Oktoberfest - the largest in the US, and 2nd largest in the world after the one in Munchen ( google it). Also spectacular views of the city downtown + some nice museums

Dayton, OH during their air show, plus the largest air museum, makes the Udvar one in IAD look super tiny. OK downtown

Indianapolis, IN and Columbus, OH - some nice things to see there as well, OSU + the race track, a lot of history.

Vancouver - Swim, Ski, Sushi, Hike, Victoria, etc. etc.

Santa Fe - Hike, Eat, Art, etc.

Dayton - Air Museum, side trip to Cinci for the Art Museum

I don't disagree...but the OP established his acceptable definition of "medium" as being cities like KC and the Twin Cities, both metro areas with over a million people.

Also to the OP: I originally threw Austin and Madison onto my list because of music. I think of both of them as much more than the typical college party scene - a little more cosmopolitan with good food, more sophisticated nightlife, etc. The colleges themselves will both have fine arts offerings. The other Big Ten towns on the list (Lansing, Columbus, etc.) will too but for some reason I find Madison more...I don't know...interesting than those. I think of Lansing as a place I'd go for a football weekend.

Kansas City will have a new performing arts center in a year or so...new home for the Lyric Opera, the KC Symphony, and perhaps the KC Ballet (not sure about the ballet...). Stay downtown or in the Crossroads district...you'll be walking distance to 40-50 small art galleries and many of the city's best restaurants.

You may be the first person I've ever run across that has said that one of their best bbq experiences occurred in St. Louis. If you like bbq, there are numerous places in Kansas City that would be worth visiting (Arthur Bryant's, Gates, Oklahoma Joe's, and Jack Stack all come to mind).

I let that slide: once he actually completes the Kansas City trip, the STL 'que will no longer seem palatable.

Interesting thread.

I'll second the recommendations re Portland, Oregon and Portland, Maine.

New Orleans, definitely.

Also, Baltimore, especially but not only if you like crab.

Charlottesville, Virginia.

I recently visited Pittsburgh briefly a couple of times, partly to visit my niece who'd started college there. I didn't see enough of the town to give a really knowledgeable recommendation, but its rivers and hillside provide a much prettier setting than I'd expected.