I know from my physics classes that gradient of a scalar points in the direction normal to a plane passing through the point or in other words it is perpendicular to constant height surface.
Imagine climbing a hill. In the following picture heights are the constant surfaces represented by planes.
But the normal to the plane passing through a point on the hill is directed into the sky through the air.
Is it actually possible to walk along this path? I mean we can't really walk upwards against gravity! But normal to the constant height surface point straight up!

Your function acts from $\mathbb{R}^2$ to $\mathbb{R}$ (the height of a given point). Through the point you have chosen, you can draw a circle on which the function is constant (assuming that the hill has the appropriate shape). The vector (in the plane $\mathbb{R}^2$) pointing to the center of the hill is really perpendicular to this circle at this point.
That is, your mistake is that you misunderstood what "constant height surface" means. We are talking about a surface (dimension $n-1$) in the domain of the function, and not anywhere in its graph.