Most bang for buck approach to insulating home
I am from the Midwest and my crew and I have done green work in a number of historical home in the area.  Some of my thoughts on your situation:


Don't ever put stuff in your walls through holes.  I don't care what kind of sales pitch you are given, don't.  My standard reaction would be, "How do you prove your installation, what r-value are you giving me, I will pay you in full once I hirer an independent auditor and they OK your job".  You will never hear from that company again.  There are too many issues for me to discuss but basically you could be putting something dangerous in your home, the chances of them filling the entire cavities are none, and whatever they use will surely get in the way if you ever remodel anything else.
If you have a basement you need to stop airflow coming into it.  Caulk any gaps that are above ground.  Rock wool all of the exterior joist cavities.  Foam board is an option but this isn't generally high reward (you will lose cooling in summer and not much cold is let in below grade).
You have basically two options for your walls.  #1 You remove siding and you just have some housewrap... So you are adding traditional insulation from the outside, rewrap, reside.  Very low materials cost - would be a 2-3 day job for a crew.  #2 You have a little extra under your siding, so getting in is harder.  3-4" XPS, tape, furring strips, reside.  I have insulated the exterior of 5 homes so far.  We stucco'ed after but you could put traditional siding on too.  This is like putting a blanket on your home and is dramatic.  To go with that - future buyers of your home will pay a premium vs. treating drilled insulation as nothing (or a problem).
New windows.  These would be installed before exterior work if doing this in chronological order.  Given that during window install that you take care of any air leaks by the windows.
Make sure there aren't major drafts in attic.  Then you need to bury your attic in blown in cellulose at 2-3 feet deep.  


I would start in your basement.  From there it comes down to - how bad is this problem?  If the cold is as noticeable as you say then you really need to get the walls insulated.  I gave you two options that work.  The first is much cheaper but not as effective (and maybe not doable on all houses).  2 &amp; 5 can be done by you for $600-800.  3 is somewhere between 3-20K but is a complete game changer for your home (plus new look).  4 depends on how many windows but you can put decent windows in most homes for 3-4k.