Very Computer

First check that DNS is working reasonably well, if it's not see if
your ISP's backup works or implement local DNS for yourself (DNS Howto
for a cacheing DNS server).

Second get irqtune, it *really* helps, it puts the serial port at top
priority.

I load an IRC-II client with Lice and get on a good IRC server in
under 5 secs depending on traffic.

A possible cause:
Some part of your system setup may be generating malformed system names
initially; when pppd
is up this bad system name is sent off to the name server at your ISP
and it struggles with it
before giving up. Then your system generates an ok system name and/or
your local
name resolver maps the name to a IP address and everybody is happy.
While it sounds
far fetched it actually happened as i was setting up my local network.

A simpler scenario may be sufficient to cause the delay:- the external
nameserver is
queried first for machines on the local network and the external
nameserver does not
know about the local machines. When pppd is not up the external name
server can not
be reached so the local name server will be queried fast; when pppd is
up the external
name server has to time out before the local name server is queried.

Run pppd with debug and watch /var/log/messages.
--
regards,
 Ramesh
(Ramesh Narayanaswamy)