The only phone I've ever had trouble installing more than a few apps was one with 512MB of storage. If I go check the second result on amazon for android phone it's a solid motorola option, unlocked for $127 and with 128GB. That's more than enough; even some flagships have 128GB.
The "just over $100" range has multiple options with good storage. Below that is a sea of locked/refurbished phones that are also good options in many cases.
Digging deeper I eventually hit a "BLU" brand phone for $50 with only 16GB, and that leaves you with not very much after the OS takes its space. But then you can add $10 to get another 16GB and have more than enough room for apps.
So you have to go really low to have the problem you're describing.
Hardware may be cheap enough now that budget phones are more useable--32 GB for <$100 is a major improvement.
Regardless, since they have a 16GB model I strongly doubt the 32GB model would ever have less than 16GB of usable space.