The resolution is: We added spanning-tree edgeport to the access ports going straight to the devices, and they booted up much quicker. Also we disabled STP on the ports to the other switch stack, which helped somewhat (the devices booted, their DHCP request didn't timeout) but were still booting slowly due to not getting an ip quickly.
Levi, did you mean to post the answer in a separate post?
It helps to understand the underlying mechanism and ramifications here.
With regular spanning-tree enabled, a port gets physical link immediately when a device is plugged in. However, no traffic will pass until the spanning-tree algorithm runs to ensure that the port won't cause a loop. This process can take up to 60 seconds. Spanning-tree assumes that there is a possibility of the new device causing a loop until it verifies that it won't. Guilty until proven innocent, then it can pass traffic.
Your terminals and some other devices will send a DHCP request shortly after getting link, and repeat it at intervals. Eventually, some end devices will give up.
When an edge device such as a host is connected to a normal spanning-tree enabled port, no traffic passes until spanning-tree runs its course resulting in slow or no DHCP establishment and the network will seem to be down for up to a minute even though physical link is up.
spanning-tree edgeport doesn't disable the spanning-tree process. It enables the port to pass traffic immediately but continues to run spanning-tree in the background. If a loop is detected, the port will be put into blocking mode. Innocent until proven guilty. So, for any port that is connected to an end device, spanning-tree edgeport is the way to go. The device comes online right away and starts its DHCP process immediately. If through a cabling error the port does become part of a bridging loop, the network disruption will be squelched when spanning-tree completes in less than a minute. So, you can bring the network down with spanning-tree edgeport, but it will recover.
Disabling spanning-tree completely on trunk links between switches is a very dangerous thing to do. If a bridging loop occurs, the entire network will be flooded and virtually unusable on all VLANs on the trunk. Because inter-switch links don't change often as opposed to ports used for laptops and the like, the extra 60 seconds for full spanning-tree operation isn't a big deal.
Normal spanning-tree ports will not pass traffic until spanning-tree completes, about a minute. Use this on links between switches and bridges.
Spanning-tree edgeport passes traffic immediately, but allows spanning-tree to run which will detect and shut down a loop.
Disabling spanning-tree will pass traffic immediately but you lose all protection against bridging loops.
Note that there are enhancements to the classic spanning tree that go through the loop detection process faster. Some of these are vendor-specific.
P.S. Be careful with wireless access ports. Two of them on the same channel, SSID, and WPA key can cause a loop if they are within radio range of each other.