Honestly, with the Treasure Valley's hills, I wouldn't go less than 36T. I can still climb an overpass fine enough with 36T, even better with 44T though. You might/should be fine with 32T tho, definitely don't go smaller than that if it's a 26" wheel - do you have a speedo'd/gps'd top speed currently? You said it feels like it wants to go faster, I'm curious how fast you're already going. As well, it could be that the back bearings are too tight or the brakes are rubbing.
Dunno how many links you'll have to take out - just take as many as it needs.
But first - what size drive chain are you running? I know 210/410 can cause some issues in clipping the sprocket teeth, 415 is wide enough to not clip the teeth, and #41 is wider than that and also much stronger.
Coolness - I'm always down to meet and help out another rider. I'll make a call tomorrow and see if it's thursday or friday I'll be in Boise.