I'm also starting at level 1 and it's worth noting that no one in the party has any social skills.
You can make a cleric startlingly socially adept at 1st level.
The herald domain (Book of Exalted deeds, p87) adds intimidate to your class skills and gives a +4 sacred bonus to diplomacy and intimidate. The domain focus alternative class feature (Dragon 347, p91) doubles the bonus provided by a domain, but removes your other domain and your ability to spontaneously cast cure spells. Combining those, you have a +8 sacred bonus to diplomacy and intimidate, and you can have 4 ranks in both skills.
The evangelist variant (Dragon 353, p88) gives you a +2 bonus on diplomacy (also comprehend languages 2/day), but removes turn undead.
If you want to go full diplomancer, you can take the bind vestige and practiced binder feats and bind Naberius. That lets you take 10 on diplomacy checks no matter what and removes the normal -10 penalty for making a rushed diplomacy check as a standard action. (All from various parts of Tome of Magic.)
Admittedly, the herald domain is hard to rectify with Naberius. The joy domain (Book of Exalted Deeds, p87) can be used instead, but you give up intimidate. Hedonism seems like a perfectly viable explanation for religiously dedicating yourself to joy and binding your soul to otherworldly entities.