That's like "what size gas tank should my car have?" Do you use it for running around town, so a 10 gallon tank is plenty, or do you drive across country a lot, so you want a large tank.
If the phone is old, it's designed for smaller apps (the larger the phone storage gets, the sloppier the "developers" get.) I wouldn't get anything less than 32GB these days, and I wouldn't get a phone that didn't support an external SD card.