Tires, Tires, Tires

If the inside edge of your current tires are going bald - you've got uneven wear and definitely need an alignment. If you don't do an alignment; you'll place that same uneven wear pattern on the new set of tires and pretty much VOID the mileage warranty. They will blame mechanical misalignment and/or suspension issues - not manufacturer's defect. This could also void your road hazard warranty.

 

To verify: your wheels are 15" diameter?

Was the head gasket replaced then? I'd recommend you clean the full EGR system as well, if it wasn't done. More info in my signature. (on a phone turn it landscape to see signatures)

 

My experience has been - tires make a HUGE difference on an EV/HEV/PHEV car, not so much on a gas or diesel car. On my 2012 Volt, I gained around 5-7MPG compared to regular all-seasons, when using Bridgestone Ecopia EP422+ tires (or 4-5MPG gain with Goodyear Assurance Fuel Max tires).

On everything else, tires don't seem to do much for MPG, unless you get into dedicated snow or off-road tires. YMMV, you should also get an alignment too like Biomed01 said to increase the life of your new tires.