The Civic CX is a obd1 car, so I'm guessing it has a four wire o2 sensor.
I'd guess that the o2 sensor is probably a major factor in your poor gas mileage as well.
The larger tires are also throwing off your speedometer so you're actually getting better gas mileage than you realize.
If you're on your original o2 sensor, I'd recomment changing it anyway. o2 sensors start working less well after 30k miles. if you're over 100k it's definately going to not work as well.
Besides that keep everything as stock as possible. Don't get a K&N air filter (unless you already have one). STick with recommended oil, gas, etc.
As for your octane, what is your altitude? Here in Salt Lake City the regular octane is 85, and that's mainly b/c of the high altitude (4000 feet). I can use 85 as long as I don't suddenly drop to sea level.
If you're around the same altitude as me anything around 85 octane is good.
The civic cx, also, has 1 wire o2 sensor, suprise suprise, matt.
That really is surprising, really. You would think that HOnda of all people would have upgraded all of their obd1 cars to at LEAST 4 wire o2 sensors. For them to make one exception (on a gas mileage giant nontheless) is a shocker).
at that time the cx was designed to be economical only, single wire o2 sensor, no bells, no whistles, no sway bars, no aerodynamic panels(lip, rear bumper block), no mudflaps, no acceleration. the vx was intended to be the real fuel saver.
83 octane gas??? that seams kinda rediculous.... anyway how is the ignition timing? fuel filter? also if your planning on cleaning your injectors, do it before. the fuel filter is cheap and easy to replace, so is the o2 if it doesnt break when you try to pull it out. the cat sucks.
EDIT: spark plug wires, how are they?
don't waste your time or time will waste you
maybe one of your brake float pins are sticky and causing your brakes to stick and drag.
you did not mention your spark plug wires, they may need to be replaced. (always always replace wires with plugs)
Your clutch may be slipping.
You may have a bad alignment (even tho it may drive straight) if your camber is out of spec, you are losing lots of energy due to the high rolling friction of lots of weight dispursed on the sides of the tread.
You may have lots of extra heavy stuff in your car.
Your tires may be underinflated (common!)
"You have to know the truth, and seek the truth, and the truth will set you free."
Just brainstorming, but do cars get worse mileage at higher altitudes? Depending on your location in MT, you may have less oxygen at your disposal, which could make it sluggish compared to before.
Other routine stuff: PCV valve (shake it, it should sound like a metal ball bouncing in there), air filter and intake should be clear (check for clogs), same for exhaust -- does it rev-up easily, or feel choked off (could be the cat or plugs/wires as mentioned earlier). This is expensive, but the fuel injectors could be giving it up. There's a whole variety, really. I feel like I'm on "Car Talk"...
"What kind of sound does it make?"
Is it burning oil? -- check the tail pipe -- wipe the outlet with a paper towel -- if it's thick/greasy, you probably have an oil burn situation. Normal is carbon-black with some moisture. Track fluids -- if you're losing coolant, it could be a blown head gasket, especially if you have a steam-look coming out of your exhaust in warm weather (like what most cars look like in the cold). Lastly, Matt had a good point about the tire/wheel size -- you're traveling more miles that you think, so you'll have to calculate the change (bigger wheel, longer it takes to complete one revolution, one revolution is used to calculate speed and mileage).
Lastly, I assume you have drum brakes in the rear -- which need adjusted from time to time. One way is to use the E-brake regularly when parking, or drive in reverse quickly and hit the brakes -- they'll auto-adjust.
At this point we can only guess and rely on your descriptions since we we can't see/drive the car.