A common cause of this problem is using the Physics resolver for determining if a character is grounded. The issue arises because the physics solver's whole purpose is to push your character and the ground apart (so they aren't inter-penetrating).
Tricks like increasing gravity work by attempting to force the character back into the ground each frame. This isn't very reliable, as you've mentioned, and increases the work of the physics engine and decreases physics stability.
Some physics engines can further attempt to resolve this problem using things like separation slop (which means the objects aren't completely pushed apart) or by maintaining a contact cache. Using these features to solve the gound detection problem can require some extra work, though; the results of testing for sloppy collision or querying the contact cache may require the use of different APIs or events than what you're currently using. I'm not super familiar with Unity physics so I can't provide any specific insight for your case.
A very generalized solution that works for almost engine is to use a separate means of detecting the ground which doesn't directly rely on your character's physics body. These can include short ray casts (e.g., shoot some rays down about 1/5th of a unit or so from the corners and center of the character's feet) to probe for the ground, or using a thin physics sensor (or several sensors) attached to the character's feet. These methods don't try to test if the character is touching the ground but instead test if the character is really close to the ground. It sounds hacky but works phenomenally well.
Using multiple rays or multiple sensors can also help you detect some interesting scenarios that the simpler physics-collision method has trouble with. For instance, if you want to detect if a character is standing on a ledge, the use of multiple rays or sensors can indicate this clearly (e.g. the left sensor indicates there's ground but the right sensor does not, thus the character is standing on a ledge).
Using several rays or sensors of increased height can supply further information. For instance, short rays might detect if the character is very near to ground (close enough that you can consider them grounded) while some slightly longer rays can indicate that the character is near ground. This can be used to inform animation, to control game features like double jump, or to help keep characters grounded when running down ramps (if the character was grounded and the next frame - no jumping involved - the character is only very near the ground, snap the character back down to the ground).
Physics engines and platformers aren't a good fit for each other. You have to muck around behind the physics engine's back using techniques like I've described to achieve that ideal Nintendo-like feel to your characters.