I tend to run 89 octane in the summer, run 36 psi in the tires instead of the 34 psi on the door tag. You might want to look for a tire with lower rolling resistance next time for new tires, could possibly push you into the 30 mpg area.
I use the lowest octane which is 85 in my state and a lot of the ones I travel too.
I still have the factory tires but I'll definitely factor in rolling resistance when I buy my own. Snow and wet road performance has to be a higher priority though for me.