I have had the same problem on different distributions with sendmail doing that, and I have found that the delay occurs when sendmail is trying to figure out (resolve) the domain name. In the configuration file, there is a line towards the top with a comment "uncomment this and enter your fully qualified domain name if sendmail can't figure it out on its own"...loosely paraphraized...real loose. When I uncommented it and put my fully qualifed name in there, it when back to being a quick process at boot up.