Wade,
In my experience of arranging trips for me and my friends or me and my wife, I strongly advise that you have a backup plan and/or side trips planned. Although many if not most people on this board would rather fish 24-7 it's my experience that most (occassional fishing) people can't handle a long trip of only fishing. So I suggest that you think about staying at a place that, in addition to fishing, has horseback riding or whitewater rafting or at least skeet shooting. Although one of my favorite places to fish is the Bitterroot Valley, I'd try to hit one of the areas with a bigger river and make sure that you float- this way the guides will have better control over the fishing and your rep won't be solely in charge of getting them into fish. Staying near Yellowstone might be a good idea (Bozeman etc). Twin Bridges is within reach of a number of rivers. As someone else mentioned, your timing is not good (many people book these at least a year out) so you are probably going to have to do some research on your own since a lot of the shops mentioned here might be booked.
One place that I have stayed that is about to become more built up is the Seeley Lake area. We stayed at the Double Arrow resort which has their own golf course and it is near the Blackfoot and other rivers in Swan Valley. Moving up in the elegance factor is Paws Up. Yes, cheesy name, but they off just about everything that you'd want to do in MT:
http://www.pawsup.com/resort/montana-fly-fishing.php

AZ