[94 Jimmy]

I wouldn't bother with a full tune-up. As you said the plugs are good for 100,000 miles, and they are. Wait to 100K or when you have a problem and then change the plugs and wires.
You can check that the intake system is clean, The Manifold Absolute Pressure sensor is there and sometimes gets bugs in it. It's an aluminum honeycom thing in the intake plumbing, check to see if it's clean. Be careful its delicate and expensive. K&N filters will clog up and still pass light through, clean and lightly oil with every oil change no matter what they look like. A dirty air filter will ruin your gas mileage, so will bad O2 sensors. If you are getting any rotton egg or burned hair smells out of the exhaust it's a sure sign that your running rich, and the oxygen sensors are usually the culprit.
You can't increase both power and milage. Gasoline is power and to get one you use the other. If you want better mileage, slow down, it'll have more effect and cost less than anything else you can do. I've been told that for every 5 mph above 55mph you lose 10% of your mileage. On a recent 50 mile trip in my Olds Silhouette at 60mph I got 30mpg, I spead up to 65 and sure enough the mileage computer droped to 26-28.
If you want power, put a Wipple Supercharger on it, it'll pass anything but a gas station.
See ya
94