I'm going through insulation woes with my 1870 house right now, and people drastically overestimate how their uninsulated walls are the issue. Your walls are most likely at least something like R-9 if not more depending on the old house you have.
The actual issues, in order of importance, are:
1. Air sealing the house. So yes, replacing and repairing windows. Not because double pane is so much better, but because your windows and doors are leaking unconditioned air into the house.
2. Roof insulation
3. Basement/crawl space insulation. Yes, this is more important than walls
4. Now you think about the walls. As you said, depending on the climate, from outside in may be safer (which can also be true for roof and basement depending on materials)