After trying everything I could think of (uninstalling apps, factory resets, etc.), I finally discovered that my issue was caused by the phones Bluetooth. When it's on, the phone's OS and various apps, including the native text messaging app ceases to function properly. When I turn it off, all text messages send immediately, and the OS starts operating normal again (apps download and update correctly, notifications arrive on-time, etc.). I didn't even suspect the problem being the Bluetooth because it's such an fundamental function, but on my phone, I was able to whittle it down to the Bluetooth being the culprit. It's been very frustrating. I've been trying to solve this problem for about 6 months now. I finally figured it out.
Btw, I have a Samsung Galaxy S8 with AT&T, purchased from Best Buy.