There is a short squealing noise (sounds like a belt maybe?) when I start the engine, but not every time. It's been happening for a few weeks now. Last week my battery was dead so I replaced it, could there be a connection there?
Yes, the squealing is most assuredly associated with the dead battery and symptoms you describe. What is probably happening is either the serpentine belt is worn out (hard to diagnose due to how it wears) and/or the tensioner pulley is not providing enough traction for the belt. On start-up, the alternator works overtime trying to charge the battery of the juice you just used to get the engine running. If the belt is making noise, this is caused from slippage. After a little bit when the battery is nearly charged the alternator isn't under as much load and the belt gets hot from the friction of slipping, it will usually stop making noise. As time goes on, the belt will make noise longer and longer upon start-up, usually due to the belt becoming more worn out.