dhcp сервер запускается раньше, чем стартовала сеть

Попробуйте так:

rc-update add net.eth0 boot
rc-update add dhcpd default

Проверьте блок depend() в /etc/init.d/dhcpd, допишите туда сетевой интерфейс за который он цепляется
типа

depend() {
        need net.ethХ
        use logger dns
}

Х - номер интерфейса

мдя. доки никто читать не хочет ;(

# It's possible to define extra dependencies for services like so
#rc_config="/etc/foo"
#rc_need="openvpn"
#rc_use="net.eth0"
#rc_after="clock"
#rc_before="local"
#rc_provide="!net"

# You can also enable the above commands here for each service. Below is an
# example for service foo.
#rc_foo_config="/etc/foo"
#rc_foo_need="openvpn"
#rc_foo_after="clock"

# You can also remove dependencies.
# This is mainly used for saying which servies do NOT provide net.
#rc_net_tap0_provide="!net"