At the beginning of an encounter, what happens if both sides are being stealthy?
The same thing that would otherwise. Both sides roll to remain unseen / notice the other group (using your flavor of passive checks / hidden rolls / whatever). Unless one of the sides actually wants confrontation, they can even pass each other like ships in the night.
Side note: you might consider giving Disadvantage to hide from someone you cannot see.