Is it possible that your DHCP server has high CPU? Did you try installing wireshark on a test device, capturing the DHCP traffic and seeing how long it takes? Is it possible that your wired device has negotiated improperly and there are errors on the switch interface?
Is it possible that there is a misnegotiation on one of your links between switches or routers, and that is causing your issue?