How long are you planning on staying? Where are you flying in and out of? How far from the park are you willing to go?

The Montana side has more appeal to me but I'm from Montana so I'm biased. Red Lodge is a very nice town that has a nice main street with shops and restaurants. I get breadsticks at the City Bakery and love Bogart's Pizza. You can buy a short term permit for fishing in Wyoming or Montana and go fishing in some of the mountain lakes outside the park. West Yellowstone is nice as well but I haven't been there in some time. Bozeman is 90 miles away and has the Museum of the Rockies with the state's paleontology lab there.