What you're describing is very likely a minor inconvenience due to ART AOT compilation (ahead-of-time compilation for the Android RunTime). In other words, when apps are installed on GrapheneOS, their code is fully compiled. On traditional Android distributions, their code can be compiled on the fly (this is called JIT compilation for "just in time"). (By code I'm referring to Dalvik bytecode, but there's no need to get too technical.)
AOSP makes the distinction between cold/hot code ("hot" = often used compared to "cold") and uses AOT/JIT depending on the situation, whereas GrapheneOS chooses to use ART AOT all the way.
This results in better security and performance, even battery life when you're running apps. The inconvenience is that app installs can take longer, especially on a lower-end device. For most apps this shouldn't take more than a minute, but some can naturally take longer than others.