I say Gaara, Naruto changed Gaara for the better in part 1 and Gaara made Naruto think about how even though he's been thru a lot, there's others who still have worst things. Their friendship became solid after Naruto helped saved Gaara. Gaara saved Sasuke from A in order to talk to Sasuke on Naruto's behalf, gave Naruto some good advice about Sasuke, Gaara used Naruto as his muse as he gave a speech that united the ninjas in the alliance, saved Naruto's life after Kurama was extracted. Shikamaru wasn't really Naruto's friend in part 1 or at least not until after the chunin exams. We see Naruto's first bond was Iruka then team Kakashi after all. No one but Iruka or Gaara actually understood Naruto's pain and related to Naruto (Sasuke did too but he made it seem like Naruto's wasn't as bad since he didn't know his parents). Place Shikamaru after Gaara tho, then Sakura, Kakashi, and Bee.