I ended up going to O'Reilly's and had them test it as well. They said the battery was bad, along with the starter and voltage regulator. I went to a mechanic and he said he was positive it was the battery. Swapped the battery and now it starts up perfectly!
I've never seen/had a bad battery impact the startup like this. Very bizarre.