Do not over fertilize. Fertilizer is not going to 'fix' your spots. I know cool season lawns very well. When I first read your question, I imagined sod being laid down without rolling to ensure proper soil/sod connection. Another possible reason for spots is snow mold or other fungus that is promoted if you fertilized with too high nitrogen just before winter.
Overseeding will not help, not right now. We need to discover the real problem before you dump anymore money into your lawn needlessly. Keep that lawn mowed once per week minimum. Sharp blades.
The key maintenance thingies are: Firstus, never ever mow below 3". 3 1/2 inches is best. This will eliminate your weed problem. The fact you 'pull' weeds regularly tells me you are mowing your grass way too short. Cool Season grasses genetically have huge root systems. Huge root systems are GREAT but they need to be FED. A plant makes its own food. Large root systems need a larger top growth, the photosynthetic factories. Too short, your cool season grasses will be stressed, weeds will move right in where competition is lame. Also, a larger top growth (3 - 4") shades the soil preventing weed seeds from germinating.
Fertilizer is NOT food. Plants make their own food via photosynthesis. Fertilizer is just the chemicals necessary for plants to make their own food. Not nutrients...chemicals; Nitrogen, Phosphorus, Potassium and then 12 or more micro chemicals. The balance of percentages of the first three are important to know...lawns need nitrogen. Other plants not so much nitrogen in relation to the P and the K.
Watering is more important than you might think. A little water every day is so wrong! Causes shallow root systems vulnerable to droughts. To water a lawn correctly is to SOAK that bed, take a shovel...you should see moisture down at least 4" deep. Now, you allow that lawn soil bed to dry out (we are talking about mature grass crops here, not baby starts).
The best test is simply to walk on your lawn. When you finally see your footprints left behind because the blades aren't as turgid as before, THEN you water again and deeply. Do not water until you see your foot prints. This trains the roots of your grass crop to grow deep and deeper as the roots work to reach the moisture lower in the soil profile. Your grass will not have to go dormant ever. Dormancy is not a good thing for your lawn. Dormancy puts huge stress on the grass plants, allows weeds to get started and thrive because your grass is unable to compete. If your lawn is trained well, you will be the only one on your block to have thick luscious green grass. btw, the length 3 - 3 1/2 inches, prevents rapid evaporation of the water you paid bucks to use and spray.
Fertilization has to be ongoing at least 3 to 4 times each season. We can discuss that if any of this seems helpful.
Aeration, pulling plugs of soil OUT of the bed, leaving them where they fall, once per year.
Did you lay the sod? Or did a company lay your sod? Do you know if anyone rolled the sod right after being laid with a water filled roller? Do you remember any rolling of the soil or sod? Let me know how this lawn was installed and by who. Whom?