Yes, change the barrel and recoil lug first. I would probably get a Shilen or Criterion from Jim Briggs as well as one of his recoil lugs. I prefer the Savage varmint contour, it's plenty thick out to 30" or so. There isn't much advantage going to a bull contour. +/- $300
Next, I would get a good stock. This will be a personal choice for you. Stockade makes great stocks for Savages. I love my Pdog/Tactical. Choate makes one similar, but I hear it is very heavy. $150-$300.
I would use a Weaver Tactical 1 piece base (20moa). They are fairly low, made in the USA, and only about $30. EGW would be my second choice for a 1 piece. Burris Xtreme bases for a 2 piece. The only rings I use are Burris Signature Zee's. They are very strong, protect the scope from ring marks, and the inserts can be used to center windage or to gain additional MOA. You'll be in about $75 or so here.
Ross Schuler makes and installs the best muzzle brakes for the money. Period. I wouldn't look anywhere else. Install your barrel, mark TDC at the muzzle, and send it to Ross.
http://home.comcast.net/~MOA_Shooters/RossMuzzleBrakes.htm
Your Leupold scope will work just fine. The glass and mechanicals are good.
At some point in the future, you may want to upgrade from the accutrigger. There are only two good upgrades. The SSS competition trigger and the Rifle Basix SAV-2. So far, no other triggers compare. The Timney and the Basix SAV-1's are not much improvement over the factory trigger.