I have 2:56 in my tempest and its just a joy to drive on the interstate. I hope to change out the 326 for a 400 but I will keep the rear gears right where there at. Just love driving the car even though it doesn't have enough power to even spin the tires..
My 68 bird has 3:36 and short 25.5 tires. It just sucks on the interstate and I tend to look for back roads to use. 55 mph isn't too bad. My plan is to go with a 8.5 with 3:08 gears for a happy compromise some point in the future..

My point is be careful on what you decide to change. An overdrive setup would be the ideal compromise as they usually have lower first gears but they wont work with your current gear. So it would be some $$$ to change both the trans and the rear.

Changing the cam for more grunt can be risky. May wipe a lobe, may run into pinging. If you have a closing event on the cam that allows more cylinder pressure at lower RPM you may run into pinging issues and the cam will most likely run out of breather well before 5500 rpm.